使用 Haskell 处理 dfs 中的后继者

Question

考虑以下 Python 函数，给定节点的后继者，该函数访问它们并收集结果。（实际上，这个逻辑将构成递归visit函数的一部分。）

from typing import Any, Callable, Tuple, List, Set
Node_key = Any
Discovered = Set[Node_key]
Result = Any

def get_successor_results(visit: Callable[[Discovered, Node_key], 
                                          Tuple[Discovered, Result]],
                          successors: List[Node_key],
                          disc: Discovered) -> List[Result]:
    results = []
    for succ in successors:
        if succ not in disc:
            disc, result = visit(disc, succ)
            results.append(result)
    return results

（就上下文而言，这将是 df-traverse 函数的一部分，给定一个图和一个函数，该函数combiner :: Node_key -> [Result] -> Result相当于构建深度优先森林并调用fold-tree combiner每棵树。）

我的问题：你会如何用get_successor_resultsHaskell 写作？

一些想法：

get-successor-results visit successors disc = 
  reverse . first . conditional-fold 
                      (\(d, _) node -> not (elem node d))
                      (cons-next-result visit)
                      (empty-set, [])
                      successors
  where
    cons-next-result visit _@(disc, results) node =
      let (disc-new, result) = visit disc node
      in (disc-new, result:results)
    conditional-fold p folder e xs = case xs of 
      {[] -> e;
       x:xs' -> if p e x then conditional-fold p folder (folder e x) xs'
                else conditional-fold p folder e xs'}

Answer 1

看起来很简单，直接翻译一下：

get_successor_results ::
    (node_key -> discovered -> Bool) ->
    (node_key -> State discovered result) ->
    [node_key] ->
    State discovered [result]
get_successor_results not_in visit successors = do
    results <- for successors $ \succ -> do
        should_visit <- gets (succ `not_in`)
        if should_visit
            then Just <$> visit succ
            else return Nothing
    return (catMaybes results)

希望与您的 Python 代码的相似之处是清楚的。这里唯一真正的变化是用作Nothing您不想访问的继任者的占位符，并作为第二步将其剥离。当然，我建议您使用驼峰命名法；这是 Haskell 中的一个强约定，因此它将更好地与现有的库调用融合在一起，但我希望相似之处尽可能明显，因此我尽可能使用与 Python 代码相同的名称。