haskell - 无限循环 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，我想你会发现它永远不会返回。这就是你的错误。

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