[Haskell-beginners] A tree code

AbdulSattar Mohammed codingtales at gmail.com
Fri Feb 24 06:16:54 CET 2012

Hello bahadyr,

Before going into data Tree alpha, consider a simpler version,  tree that
stores only an integer in it.

Now, a (binary) tree will consist of nodes. A node can be an Empty node or
store an integer and link to two other nodes (a left one and a right one).
So, basically we have only two types of nodes. We represent this in this

data Node = Empty
          | ValueNode Int, Node, Node -- An integer, a left node and a
right node

We construct this node this way:
n = Empty --creates an empty node
n = ValueNode 3, Empty, Empty -- A node containing only one value
n = ValueNode 3, (Node 4 Empty Empty), (Node 5 Empty Empty) -- 3 with left
4 and right 5

This has a limitation: we can store only integers in it. Let's remove that
limitation by using Type Variables.
Instead of saying that Node stores only Int, we must say that Node needs a
Type first, then it stores values of that type in it.

So, instead of just:

data Node

we have

data Node a = Empty -- a is the type variable

Now, Node uses that a instead of Int

data Node a = Empty
            | ValueNode a, (Node a), (Node a)

(Node a), (Node a) tell that the left and right of the trees must be of
type (Node a) i.e. it cannot left cannot have an Int while right has a
Char. The whole tree holds the same type.

The creation of objects is same as above. The types of x and y would now be x
:: Node Int, y::Node Int

We can now have:
c = ValueNode ("haskell", Empty, Empty) too.

Hope you are clear on this and welcome to Haskell!

On Fri, Feb 24, 2012 at 10:20 AM, bahadýr altan <doaltan at yahoo.co.uk> wrote:
> Hello. There is a code below and I couldn't understand it myself. Could
> help me with that please?  I especially have no idea about "data Tree
> = Empty | Node " part.
> data Tree alpha = Empty | Node ( alpha ,Tree alpha , Tree alpha )
> x = Node (1,Node (2,Empty ,Empty),Node(3,Empty ,Empty))
> y = Node(3,Empty ,Empty)
> Thanks in advance
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners

Warm Regards,

AbdulSattar Mohammed
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120224/a64eeea6/attachment.htm>

More information about the Beginners mailing list