无限循环 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

让我怀疑 if 的 "then" 部分。我一直在努力解决这个问题，如果有任何帮助，我们将不胜感激。

Answer 1

在盯着你的代码多年试图弄清楚它应该做什么以及它为什么会卡住之后，我想我意识到了这个问题。

nodeF 指向 nodeA。（我才刚刚意识到！）您似乎正在尝试使用 == 运算符来确定您何时返回到您已经查看过的节点。那不行。

当你说node1 == node2时，==运算符会遍历整棵树，看两个值是否相等。如果它们是相等，并且这个结构包含一个无限循环......好吧，那么你的代码将永远循环！尝试一下。如果你问 nodeA == nodeA，我想你会发现 never returns。这是你的错误。

解决此问题的唯一方法是在每个 Node 上放置一个真正 独特的 标签，并仅比较标签。您无法检查 Haskell 中的两个变量 "point to" 是否相同；只能比较两个结构体是否有相同的值，也就是完全遍历。

无限循环 Haskell

Infinite Loop Haskell

haskell

infinite-loop

ghci