CODEWITHSUNDEEP
haskelldepth-first-searchfold
Eric Auld
Eric Auld

Reputation: 1244

Processing successors in dfs with Haskell

Consider the following Python function, which, given the successors of a node, visits them and collects the results. (In practice this logic would form a part of the recursive visit function.)

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

(For context, this would be part of a df-traverse function which, given a graph and a function combiner :: Node_key -> [Result] -> Result would be equivalent to building the depth-first forest and calling fold-tree combiner on each tree.)

My Question: How would you write get_successor_results in Haskell?

Some ideas:

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'}

Upvotes: 3

Views: 165

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 153087

Looks pretty straightforward to translate it directly:

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)

Hopefully the parallels with your Python code are clear. The only real twist here is to use Nothing as a placeholder for successors you don't want to visit and strip them away as a second step. Of course, I recommend that you use camel-case names; that's a strong convention in Haskell, so it will blend in better with existing library calls, but I wanted the parallels to be as obvious as possible so I used the same names as your Python code wherever possible.

Upvotes: 6

Related Questions