### Data Types

In MiniML: `bool`, `int option`, `int list`

`datatype shape = Circle of real * real * real`

### Recursive Types

• Context-free Grammar
• Inductive (leaves are just ints)

### Using Abstraction

Fold is your friend! `fold` takes a list, state (accumulator), and a folder.

internal function loop.

base case: empty list

induction step: apply folder to (head, state), and recursively call loop on the tail

map:

### Pattern Matching

like switches except not just on ints (or enums)

can be:

```case s
of x => e1 (* any subject matches this pattern *)
| _ => e2 (* same as x but discarded *)
| 3 => e3 (* matches when s = 3 *)
| (p1, p2, pn) => e4 (* provided s is a tuple
* and the correct arity
* (guaranteed already by
*  the type checker)
* pn can be a pattern
*)
| C y => e5 (* Matches Constructor AND
* y can be a tuple, constructor,
* record, etc.
*)```

### Quirks

```case s
of (1, 2) => e1
| (1, 3) => e2```

A naive compiler would ask “Is the 1st element 1?” twice. In general, this is NP complete.

### Infeasible/Silly

```case s
of x => e1
| 3 => e2```

x will always match

```fun diff(nil, y) = y(1)
| diff(x, nil) = x(1)```

Overlapping `(nil, nil)` so y(1) will never be executed.

### Questions?

```case s
of Cons(x)      => e (* 1-tuple = variable *)
| Cons(y, nil) => e (* redundant *)```

One cannot call functions ins a pattern, or match on the value of a ref. However, SML lists can be deconstructed using `::` as in the following:

```case s
of []         => e (* empty list *)
| hd :: tail => e (* non-empty list *)```

### Example

```case s : (bool * intlist)
of (true, _)            => p1
| (false, nil)         => p2
| (false, Cons(x,Nil)) => p3
| (false, Cons(y,z))   => p4```

#### Is the order of matching important?

If the ordering is right to left, then the correct match will not happen until both arguments are matched (since `_` is the wildcard)

#### Are p3, p4 redundant?

No, because p3 is more specific but overlapping. It matches specifically Nil while p4’s last argument matches anything and assigns the value to y

#### Is `case s of x => e | 3 => e` redundant?

Yes, because x will always match because of ordering and 3 will never