# Algebraic data type

(Difference between revisions)

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