CODEWITHSUNDEEP
haskelltree
user6264051
user6264051

Reputation:

How does a non-binary-tree work in Haskell?

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.

Upvotes: 1

Views: 348

Answers (1)

user1984
user1984

Reputation: 6808

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 []]

Upvotes: 2

Related Questions