# Pattern Matching

*By Kaz Zhou, September 2020*. *Revised May 2021*

Patterns take on many appearances, such as:

- Constants:
`150`

- Variables:
`x`

- Wildcard:
`_`

- Tuples:
`(true, _)`

- Constructors (which may contain other patterns):
- Lists:
`x::xs`

- Other datatypes:
`Node(L,x,R)`

- Lists:

Patterns can be matched against values to form bindings. Consider the following declaration:

`val (x,y) = (1,2)`

The result is that `1`

gets bound to `x`

, and `2`

gets bound to `y`

.

Pattern matching may fail. For example, the following raises exception `Bind`

.

`val 10 = 9`

Besides `val`

declarations, pattern matching is also used in function declarations, lambda expressions, and case expressions.

## Function declarations:

```
fun fact 0 = 1
| fact n = n * fact(n-1)
```

The function `fact`

is given an `int`

as input. If the input successfully matches the pattern `0`

, then the function returns `1`

. Otherwise, the input is matched with the pattern `n`

, binding the input to `n`

. For example, if we evaluate `fact 5`

, then `5`

is bound to `n`

, so the expression becomes `5 * fact(4)`

.

Each clause of the function declaration tells `fact`

what it should do, depending on the input. The bar, `|`

, acts as a separator between the two clauses.

Note that it's important for your patterns to be *exhaustive*. The above function is fine, because all values of type `int`

can match with either `0`

or `n`

. However, suppose we had the following function:

```
fun fiction 1 = 1
| fiction 2 = 2
| fiction 3 = 6
```

There are many inputs which do not match with either `1`

, `2`

, or `3`

. For example, `fiction 4`

would raise exception `Match`

.

A more subtle bug is when patterns are redundant. The following example has the clauses of `fact`

swapped.

```
fun factloop n = n * factloop(n-1)
| factloop 0 = 1
```

The second clause of `factloop`

never gets executed! When evaluating `factloop 0`

, SML will try to match `0`

to each pattern, *in order*. Therefore, `factloop 0`

steps to `0 * factloop(-1)`

, because `0`

can match to `n`

. Convince yourself that `factloop k`

will loop forever for any `k`

of type `int`

!

## Lambda expressions:

`(fn [] => false | x::xs => true) [1,2,3]`

The lambda expression is similar to a function, as it turns an input into an output. In the example above, `[1,2,3]`

is the input. It doesn't match with `[]`

, but it does match with `x::xs`

. Namely, `1`

gets bound to `x`

, and the list `[2,3]`

gets bound to `xs`

. As a result of this successful pattern matching, the lambda expression returns `true`

.

You should still make sure your patterns are exhaustive. For example, the following expression raises exception `Match`

:

`(fn [] => false) [1,2,3]`

## Case expressions:

```
fun fact' x =
case x of
0 => 1
| n => n * fact' (n-1)
```

First, note that `fact'`

does the same thing as `fact`

. However, it uses an extra `case`

expression.

Let's consider what happens when we evaluate `fact' 5`

. First, `5`

gets bound to `x`

. Then, the `case`

expression tries to match `5`

to a pattern. In this scenario, `5`

successfully pattern matches with `n`

, so `5`

gets bound to `n`

. Therefore, `fact' 5`

evaluates to `5 * fact' 4`

.

As usual, the patterns in `case`

expressions should be exhaustive.