# Difference between revisions of "Algebraic data type"

BrettGiles (talk | contribs) m (Adding glossary category) |
Misterbeebee (talk | contribs) |
||

Line 36: | Line 36: | ||

</haskell> |
</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 arbitrary an dinternally 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. |
||

+ | |||

==See also== |
==See also== |
||

*[[Abstract data type]] |
*[[Abstract data type]] |

## Revision as of 13:09, 25 July 2008

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

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 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 arbitrary an dinternally varying branching factor (0,1,2, or more).