Personal tools

Algebraic data type

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (Binary search tree: link update)
(Adding a see also)
Line 38: Line 38:
 
The two representations are almost equivalent, with the exception that the
 
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.
 
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==
  +
*[[Abstract data type]]
  +
*[[Concrete data type]]
  +
*[[Concrete view]]
  +
*[[Indirect composite]]
 
[[Category:Language]]
 
[[Category:Language]]

Revision as of 22:12, 20 December 2006

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

Contents

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

The two representations are almost equivalent, with the exception that the

binary search tree
Tip
is not representable in this
Rose
type declaration. Also, due to laziness, I believe we could represent infinite trees with the above declaration.

2 See also