无限环Haskell

Question

data Node = Node Char [Node] deriving(Eq)

nodeA = Node 'A' [nodeB, nodeC, nodeD]
nodeB = Node 'B' []
nodeC = Node 'C' [nodeE, nodeF]
nodeD = Node 'D' []
nodeE = Node 'E' [nodeB]
nodeF = Node 'F' [nodeA]

deepTraverse :: Node -> [Char]
deepTraverse (Node c []) = [c]
deepTraverse (Node c ns) = c:(map (\(Node cl nsl)->cl) (buildNodeList (Node c ns) ns))
             where lssToLs lss = foldr (++) [] lss
                   buildNodeList nw nsw = lssToLs (map (\(Node cl nsl)->(if (Node cl nsl) == nw then [(Node cl nsl)]
                                                                         else ((Node cl nsl):(buildNodeList nw nsl)))) nsw)

main :: IO()
main = putStrLn (show (deepTraverse nodeA))

每当我调用deepTraverse nodeA时，循环就会被挂起。在ghci，它确实吐出了：

Main*> "ABCEBF

让我怀疑“那么”的一部分。我对这个问题已经有一段时间了，任何帮助都将不胜感激。

Answer 1

在盯着你的代码看了很久之后，我想我意识到了这个问题。

nodeF指向nodeA。(我才意识到这一点！)似乎您正在尝试使用==操作符来确定当您返回到您已经查看过的节点时。那不管用。

当您说node1 == node2时，==运算符将遍历整个树，以查看这两个值是否相等。如果它们相等，并且这个结构包含一个无限循环..。那么你的代码就会永远循环！试试看。如果你问nodeA == nodeA，我想你会发现它永远不会回来。这是你的虫子。

解决这个问题的唯一方法是在每个Node上放置一个真正独特的标签，并且只比较这些标签。您不能在Haskell中检查两个变量是否“指向”相同的东西；您只能比较两个结构是否具有相同的值，这意味着完全遍历它们。