Algebraic data type

(Difference between revisions)

Current revision

This is a type where we specify the shape of each of the elements.

Suppose we want to represent the following tree:

We may actually use a variety of Haskell data declarations that will handle this.

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.

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).

@@ Line 24: / Line 24: @@
 </haskell>
-To maintain the order, such a tree structure is usually paired with a [[Smart constructor]].
+To maintain the order, such a tree structure is usually paired with a [[Smart constructors | smart constructor]].
 ===Rose tree===
-Alternatatively, it may be represented in what appears to be a totally different stucture.
+Alternatively, it may be represented in what appears to be a totally different stucture.
 <haskell>
 data Rose a = Rose a [Rose a]
 </haskell>
-In this case, the examlple tree would be:
+In this case, the example tree would be:
 <haskell>
 retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []]
 </haskell>
-The two representations are almost equivalent, with the exception that the
+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).
-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.
-[[Category:Language]]
+==See also==
+*[[Abstract data type]]
+*[[Concrete data type]]
+*[[Concrete view]]
+*[[Indirect composite]]
+[[Category:Language]] [[Category:Glossary]]