使用extendedRecursionEngine定义reachableFrom图

Question

我正在尝试使用extendedRecursionEngine来定义reachableFrom。携带已经沿着路径展开的节点列表是有用的。在递归过程中传递的值是一对(node_to_be_expanded，nodes_already_expanded)。

到目前为止，这就是我所能描绘的。我不知道如何实现它，所以我可以运行它而不会出现错误。

reachableFrom graph startNode = 
   extendedRecursionEngine
      (\ (node, expanded) ->         -- Stop if we have already expanded this node.
      (\ (node, _) -> Node node [])  -- If we are done, construct a Tree Node with no descendents.
      Node                           -- Build a Tree Node from a graph node and the returned subtrees.
      (\ (node, _) -> node)          -- Save the graph node for the reduceFn.
      (\ (node, expanded) ->         -- Construct a list of nodes that can be reached in one step.
                                     -- Also add the current node to expanded.
      (startNode, [])                -- Start at the start node. expanded is initially empty.

当我们从它运行reachable时，应该给出如下输出

> reachableFrom exampleGraph 2
Node 2 [ Node 3 [ Node 5 [ Node 2 []                     -- Don't expand 2 again.
                         , Node 6 []
                         ]
       , Node 4 [ Node 1 [ Node 2 []]]                   -- Don't expand 2 again.
       ]

> reachableFrom exampleGraph 4 
Node 4 [ Node 1 [ Node 2 [ Node 3 [ Node 5 [ Node 2 []   -- Don't expand 2 again.
                                           , Node 6 []
                                           ]
                         , Node 4 []                     -- Don't expand 4 again.
                         ]
                ]
       ]

> reachableFrom exampleGraph 5 
Node 5 [ Node 2 [ Node 3 [ Node 5 []]                    -- Don't expand 5 again.
                , Node 4 [ Node 1 [ Node 2 []]]          -- Don't expand 2 again.
                ]
       , Node 6 []
       ]       

其中exampleGraph和树被定义为

-- Nodes are not declared explicitly. A value of type a is a node.
-- The nodes are linked by Links: (node_a, node_b)
data Tree a = Leaf | Node a [Tree a]
type Link a = (a, a)
data (Eq a, Show a) => 
     Graph a = Graph {nodes :: [a], links :: [Link a]} 
     deriving (Show, Eq)
-- A Graph is a collection of values (of type a) with Links joining them.

exampleGraph = 
  let node1 =  1      
      node2 =  2       
      node3 =  3       
      node4 =  4       
      node5 =  5       
      node6 =  6       
  in Graph [node1, node2, node3, node4, node5, node6] 
           [ (node1, node2)
           , (node2, node3)
           , (node2, node4)
           , (node3, node5)
           , (node5, node2)
           , (node4, node1)
           , (node5, node6)
           ]

这就是当我运行这个程序时发生的事情。

> exampleGraph 
Graph {nodes = [1,2,3,4,5,6], links = [(1,2),(2,3),(2,4),(3,5),(5,2),(4,1),(5,6)]}

当我试图定义reachableFrom时，我遇到了这个实用函数，它返回给定节点直接链接到的节点。

linksFrom :: (Eq a, Show a) => Graph a -> a -> [a]
linksFrom graph node = [n2 | (n1, n2) <- links graph, n1 == node]

我不确定我是否可以用它来定义我的reachableFrom。如何使用此recursionEngine实现reachableFrom？

Answer 1

好的，玩了一段时间后，我得到了答案。下面是我们如何定义reachableFrom函数。

reachableFrom graph startNode = 
   extendedRecursionEngine
      (\ (node, expanded) -> node `elem` expanded )       -- Stop if we have already expanded node.
      (\ (node, _) -> Node node [])  -- If we are done, construct a Tree Node with no descendents.
      Node                           -- Build a Tree Node from a graph node and the returned subtrees.
      (\ (node, _) -> node)          -- Save the graph node for the reduceFn.
      (\(node, expanded) -> [ (myNode, node:expanded) | myNode <- linksFrom graph node ])       -- Construct a list of nodes that can be reached in one step. myNode
                                     -- Also add the current node to expanded.
      (startNode, [])               -- Start at the start node. expanded is initially empty.