Difference between revisions of "Algebraic data type"
BrettGiles (talk | contribs) (Adding a see also) |
m (→Rose tree: whitespace) |
||
| (4 intermediate revisions by 4 users not shown) | |||
| Line 27: | Line 27: | ||
===Rose tree=== |
===Rose tree=== |
||
| − | + | Alternatively, it may be represented in what appears to be a totally different stucture. |
|
<haskell> |
<haskell> |
||
data Rose a = Rose a [Rose a] |
data Rose a = Rose a [Rose a] |
||
</haskell> |
</haskell> |
||
| − | In this case, the |
+ | In this case, the example tree would be: |
<haskell> |
<haskell> |
||
retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []] |
retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []] |
||
</haskell> |
</haskell> |
||
| + | 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 arbitrary and internally varying branching factor (0,1,2, or more). |
||
| − | The two representations are almost equivalent, with the exception that the |
||
| + | |||
| − | binary search tree <hask>Tip</hask> is not representable in this <hask>Rose</hask> type declaration. Also, due to laziness, I believe we could represent infinite trees with the above declaration. |
||
==See also== |
==See also== |
||
*[[Abstract data type]] |
*[[Abstract data type]] |
||
| Line 43: | Line 43: | ||
*[[Concrete view]] |
*[[Concrete view]] |
||
*[[Indirect composite]] |
*[[Indirect composite]] |
||
| − | [[Category:Language]] |
+ | [[Category:Language]] [[Category:Glossary]] |
Revision as of 09:23, 2 February 2012
This is a type where we specify the shape of each of the elements.
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.
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.
Rose tree
Alternatively, it may be represented in what appears to be a totally different stucture.
data Rose a = Rose a [Rose a]
In this case, the example tree would be:
retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []]
The differences between the two are that the (empty) binary search tree Tip is not representable as a Rose tree, and a Rose tree can have an arbitrary and internally varying branching factor (0,1,2, or more).