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))
Whenever I call deepTraverse nodeA it loops gets hung up. In ghci it does spit out:
Main*> "ABCEBF
Leading me to suspect the "then" part of the if. I have been banging my head against this problem for a while, any help would be appreciated.
After staring at your code for ages trying to figure out what it's supposed to do and why it's getting stuck, I think I realise the problem.
nodeF points back to nodeA. (I only just realised that!) It seems you're trying to use the == operator to figure out when you arrive back at a node you already looked that. That won't work.
When you say node1 == node2, the == operator will traverse the entire tree to see whether the two values are equal. If they are equal, and this structure contains an infinite loop... well, then your code loops forever! Try it. If you ask nodeA == nodeA, I think you'll find it never returns. There's your bug.
The only way to fix this is to put a genuinely unique label on every Node, and compare only the labels. You can't check whether two variables "point to" the same thing in Haskell; you can only compare whether two structures have the same value, which means traversing them completely.