Algebraic data type
|Line 36:||Line 36:|
The differences between the two are that the (empty) binary search tree <hask>Tip</hask> is not representable as a <hask>Rose</hask>tree, and a Rose tree can have
The differences between the two are that the (empty) binary search tree <hask>Tip</hask> is not representable as a <hask>Rose</hask>tree, and a Rose tree can have an varying branching factor (0,1,2, or more).
Revision as of 16:45, 19 November 2008
This is a type where we specify the shape of each of the elements.
1 Tree examples
Suppose we want to represent the following tree:
5 / \ 3 7 / \ 1 4
We may actually use a variety of Haskell data declarations that will handle this.
1.1 Binary search tree
In this example, values are stored at each node, with smaller values to the left, greater to the right.
data Stree a = Tip | Node (Stree a) a (Stree a)
and then our example tree would be:
etree = Node (Node (Node Tip 1 Tip) 3 (Node Tip 4 Tip)) 5 (Node Tip 7 Tip)
To maintain the order, such a tree structure is usually paired with a smart constructor.
1.2 Rose tree
Alternatatively, it may be represented in what appears to be a totally different stucture.
data Rose a = Rose a [Rose a]
In this case, the examlple tree would be:
retree = Rose 5 [Rose 3 [Rose 1 , Rose 4], Rose 7 ]