# Algebraic data type

This is a type where we specify the shape of each of the elements. Wikipedia has a thorough discussion. "Algebraic" refers to the property that an Algebraic Data Type is created by "algebraic" operations. The "algebra" here is "sums" and "products":

- "sum" is alternation (
`A | B`

, meaning`A`

or`B`

but not both) - "product" is combination (
`A B`

, meaning`A`

and`B`

together)

Examples:

`data Pair = I Int | D Double`

is just one number, either an`Int`

or else a`Double`

. In this case, the tags`I`

and`D`

are used (in constructors and pattern matching) to distinguish between the two alternatives.`data Pair = P Int Double`

is a pair of numbers, an`Int`

and a`Double`

together. The tag`P`

is used (in constructors and pattern matching) to combine the contained values into a single structure that can be assigned to a variable.

Sums and products can be repeatedly combined into an arbitrarily large structures.

Algebraic Data Type is not to be confused with *Abstract* Data Type, which (ironically) is its opposite, in some sense. The initialism "ADT" usually means *Abstract* Data Type, but GADT usually means Generalized *Algebraic* Data Type.

## 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. The choice of algebraic data types determines its structural/shape properties.

### 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 structure.

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