# Section 10

## Algebraic Data Type

It is a kind of composite type, which means it is formed by combining other types. Two main classes of algebraic data type are product types and sum types.

- Product Types
The values of this type typically contain several values/fields. e.g. tuple type, record type. It is called "product" because the set of values of a product type, is the set-theory product of all values of its fields. e.g. the set of values of this tuple

`(int, bool)`

is formed by computing Cartesian product of`{all integers} * {all boolean values}`

.- Sum Types
The values of this type are typically grouped into different

**variants**. Those possible values of a variants is defined by its corresponding constructor. It is called sum type because the values of a sum type is a union/sum of values of those variants.- Pattenr Matching
It is used to identify a value by its constructor or field name.

### Examples

```
data Tree = Empty
| Leaf Int
| Node Tree Tree
```

Here, we are defining a data type called `Tree`

, and its possible values are splited into three different variants, which are defined by three constructors `Empty`

, `Leaf`

and `Node`

. `Empty`

takes no parameter and generates a value of type `Tree`

. It carries no data. `Leaf`

takes an integer, and returns a value of type `Tree`

. It carries one piece of data of type integer. `Node`

takes two values of type `Tree`

itself, and return another value of type `Tree`

. It takes two pieces of data of type `Tree`

, and it is recursive.

When building a value of `Tree`

, we are carring data by using constructors. We can later retrieve those data by destructing them, which is exactly the **pattern matching** mentioned in the lecture. By matching, we know which variant the value belongs to, therefore we know which constructor is used to build that value, and further more we know what data is carried by this constructor.

```
depth :: Tree -> Int
depth Empty = 0
depth (Leaf n) = 1
depth (Node l r) = 1 + max (depth l) (depth r)
```

And you can think of that as

```
int depth (Tree data) {
switch (data.constructor) {
case Empty:
return 0;
case Leaf:
int n = data.field1
return 1;
case Node:
int l = data.field1
int r = data.field2
return 1 + max (depth (l), depth (r));
}
}
```

## Excerise

- Define a single linked list.
- Define a function that get the n-th element of that list.
- Define a function that reverse the list.

```
data List = Nil
| Cons Int List
deriving Show
list_len :: List -> Int
list_len (Nil) = 0
list_len (Cons _ l) = 1 + list_len (l)
list_get :: (List, Int) -> Int
list_get ((Cons d _), 1) = d
list_get ((Cons _ l), n) = list_get (l, (n - 1))
list_reverse :: List -> List
list_reverse_do :: (List, List) -> List
list_reverse (l) = list_reverse_do (l, Nil)
list_reverse_do (Nil, l) = l
list_reverse_do (Cons a l, b) = list_reverse_do (l, Cons a b)
```