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.

CodePudding user response：

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