# Algebraic data type

### From HaskellWiki

(Difference between revisions)

m |
m (→Rose tree: whitespace) |
||

(One intermediate revision by one user not shown) | |||

Line 27: | Line 27: | ||

===Rose tree=== | ===Rose tree=== | ||

− | + | Alternatively, it may be represented in what appears to be a totally different stucture. | |

<haskell> | <haskell> | ||

data Rose a = Rose a [Rose a] | data Rose a = Rose a [Rose a] | ||

</haskell> | </haskell> | ||

− | In this case, the | + | In this case, the example tree would be: |

<haskell> | <haskell> | ||

retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []] | retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []] | ||

</haskell> | </haskell> | ||

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

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

## Revision as of 09:23, 2 February 2012

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

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

Tip

Rose