Example:

```
datatype newtype =
TwoInts of int*int
| Str of string
| Pizza
```

`newtype` is a new type that is added to the environment.

`TwoInts, Str, Pizza` are constructors.

`TwoInts` and `Str` are also functions:

`TwoInts : int*int -> newtype`

`Str : string -> newtype`

`Pizza` has type newtype.

Usage:

```
val a = Str "hi"
val b = Str
```

`a` has type `Str "hi" : newtype`.

So the value has two components:

- Tag (which constructor)
- Data (value)

## Examples of Datatypes

### Enumerations

```
datatype suit = Club | Diamond | Heart | Spade
```

### Student Records

```
datatype id = StudentNum of int
| Name of string * (string option) * string
```

We can now identify a student either through an ID or a first and last name (middle is optional). But we cannot do both.

This is better than having a record with all these fields, but setting StudentNum to -1 if (s)he does not have one!

Obviously, this datatype does not work if every student has both a name and ID.

### Recursive Definitions

```
datatype exp = Constant of int
| Negate of exp
| Add of exp*exp
| Multiply of exp*exp
Add (Constant(10+9), Negate(Constant 4))
```

Here is how to evaluate an expression:

```
fun eval e =
case e of
Constant i => i
| Negate e2 => ~ (eval e2)
| Add (e1, e2) => (eval e1) + (eval e2)
| Multiply (e1, e2) => (eval e1) * (eval e2)
eval(Add(Constant(3), Constant(4)))
```

Note: A fully recursive function with no `if` conditions!

### Lists

```
datatype my_int_list = Empty
| Cons of int * my_int_list
val x = Cons(4, Cons(23, Cons(2008, Empty)))
```

In real lists, `[]` and `::` are merely constructors. So you can do:

```
fun sum_list xs =
case xs of
[] => 0
| x:xs' => x + sum_list xs'
```

This is preferred to `hd, tl` and `null`, as pattern matching will
catch the lack of all cases, or redundant cases, etc. It also ensures
not having to worry about exceptions if you call `hd` on an empty
list, etc.

Note that `::` is infix.

## Polymorphic Datatypes

`[]` and `::` are polymorphic type constructors. They can be used
for *any* type.

This is how options are defined:

```
datatype 'a option = NONE | SOME of 'a
```

Here is how you would define a tree of any type:

```
datatype ('a, 'b) tree = Node of 'a*('a,'b) tree * ('a,'b) tree
| Leaf of 'b
```

If it is a `Node`, it has a value and a left and a right subtree. This
definition allows the leafs to have a different type from the nodes.

Below is how you would define a list.

```
datatype 'a mylist = Empty | Cons of 'a * 'a mylist
```