1

I'm currently learning Haskell and I have a hard time grasping how Non-Binary Trees work (I'm not that familiar with Binary Trees either but I've managed to get a rudimentary understanding for it).

so I have defined the following datatype:

data Tree = Node a [Tree]

I'm struggling with understanding how the datatype "Tree" is set up in the memory, how you call it and how I should reference a list of [Tree] in my first Node a.

The following example does not work and it illustrates where I have issues with grasping tree structures in Haskell:

t1 = Node 10
t2 = Node 20
t3 = Node 30 [t1, t2]

I'm a lot more comfortable with how object oriented languages handles trees and I would be really grateful if someone could explain and make comparisons to an object oriented language.

Improve this question

1 Answer 1

Reset to default
2

Your data type definition is wrong and won't compile. It needs to be as follows:

data Tree a = Node a [Tree a]

The you can use it as follows:

λ> t1 = Node 10 []
λ> t2 = Node 20 []
λ> t3 = Node 30 [t1, t2]

The reason that data Tree = Node a [Tree] is not correct is that you are referencing an undefined variable a in the constructor which must be set in the type constructor. In addition, since [] accepts elements of type Tree a, Tree a must be set inside [].

The reason the value declarations doesn't work, aside from the with the data daclaration, is that every Node constructor takes 2 arguments while you are passing in just one here t1 = Node 10. Even if there are no children to a node, you need to give it the empty list as an argument.

Now, for demonstration purposes if we change the data type to the following:

data Tree a = Node a [Tree a] deriving Show

We can print the output of t3:

λ> t1 = Node 10 []
λ> t2 = Node 20 []
λ> t3 = Node 30 [t1, t2]
λ> t3
Node 30 [Node 10 [],Node 20 []]
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

thank you for you answer, it clarified a lot for me.
you're welcome :D. I also learn a lot by looking into these problems and trying to find the solution.
Could I ask you a follow up question? If I want to pass my tree into a function and walk through my trees within [] how would I do that? For a BinaryTree that is data BSTree leaf | Node (BSTree left) (BSTree right) with function sumTree :: BSTree -> Integer I would just call sumTree with left and right to walk down the tree, but how do I do that in my tree above?
Your children are wrapped in a list (Foldable), so you need to use a function of the fold family and similar, or you need to explicitly recurse over the elements of the list and keep in mind that each of those elements are also Tree nodes and need to be checked recursively.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.