Définir reachableFrom en utilisant extendedRecursionEngine

Question

J'essaie de définir reachableFrom en utilisant extendedRecursionEngine. Il est utile d'avoir une liste de nœuds qui ont déjà été développés le long d'un chemin. La valeur transmise au cours de la récursivité est une paire (node_to_be_expanded, nodes_already_expanded).

Voici ce que j'ai pu faire jusqu'à maintenant. Je ne sais pas comment l'implémenter pour pouvoir l'exécuter sans erreur.

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. 

lorsque nous courons accessible à partir, il devrait donner quelque chose comme

> 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 [] 
     ]  

où exampleGraph et l'arbre sont définis comme

-- 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) 
      ] 

C'est ce qui se passe quand je lance ce programme.

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

Quand je tentais de définir reachableFrom, je suis tombé sur cette fonction utilitaire qui renvoie les noeuds d'un lien de nœud donné directement. Je ne suis pas sûr si je pourrais l'employer en aucune manière pour définir mon reachableFrom. Comment puis-je implémenter reachableFrom en utilisant ce recursionEngine?

Answer 1

Ok Après avoir joué avec pendant un moment, j'ai eu la réponse. Voici comment nous définissons reachableFrom fonction.

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.