2 
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.

Improve this question
3
  • 1
    Tip: lssToLs is identical to the standard concat function. Also, there's a function called concatMap. None of which has anything to do with your bug; it's just a passing comment. Commented Oct 27, 2015 at 21:56
  • Thank you, I tested the fixed version as alluded to in my comments on the answer given by @MathematicalOrchid with concat, and it does indeed work the same. Forgot to check the prelude functions for that one. Commented Oct 27, 2015 at 22:08
  • See also: graph representation, detecting sharing, equality-testing on infinite structures. Commented Oct 28, 2015 at 0:18

1 Answer 1

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

I thought that it would test the data type's constructor to see if they are equal. But then I suppose that means that it will expand the node list's elements constructors. Hence the loop. I think I will test if the Char parts of node are equal. Also sorry I did say in the question that the data type represents a directed graph. And that the deep traverse is designed to move through the graph and backtrack when it reaches a dead end, stopping when it gets back to the starting node.
If the character labels are supposed to be unique then yes, this is the correct solution.
Yes, I have notice this issue. The work is for University, so I shall have to ask my lecturer if this is the case. Although, as the question states the Char value in the node declarations names I would imagine this to be the case.
@James "I thought it [(==)] would test the data type's constructor to see if they are equal." But your data type only has one constructor, hence any two values have the same constructor; so I don't believe that's what you thought!
@DanielWagner I meant the constructor for the constant, not the type. e.g. Node 'A' [nodeB, nodeC, nodeD] not Node Char [Node]
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.