## The Game of Pattern Matching

by Phil Freeman on 2017/10/28

Here is a simple game for two players which you might like to play at your next Haskell meetup.

### Setup

First, the two players agree on an algebraic data type, expressible in Haskell. Recursive types tend to work best.

For example, we might choose the type of `[()]`

of lists of elements of type `()`

.

### Gameplay

The goal is to write an exhaustive function `f`

from the chosen type to `()`

, by pattern matching. The return type isn't important, so I use `()`

here arbitrarily.

So the players agree on the type signature:

```
f :: [()] -> ()
```

Player one goes first, and writes down the first line of the function, which consists of a pattern recognizing some subset of the values of the chosen type.

For example, player one might choose the following:

```
f (_ : _ : _) = ()
```

Notice that the only thing which is important here is the pattern itself.

Player two goes next, but there is an additional rule - a player cannot introduce a *redundant pattern*. For example, it would be an illegal move for player two to write down the pattern `(_ : _ : _ : _)`

at this point, since that pattern doesn't match any new values.

Play continues in this way, and the last player to write down a non-redundant pattern loses.

So, for example, player two might legally write down the next line as:

```
f [] = ()
```

forcing player one to cover the only remaining case:

```
f [_] = ()
```

and so player two would win.

### Explanation

This game is an example of a poset game, where the poset is given by the choice of type. It generalizes Nim, since choosing an N-ary sum of natural numbers recovers a game of Nim with N heaps.

It is possible for gameplay to go on indefinitely. For example, in the game above, the players could alternately choose patterns matching lists of increasing fixed length: `[]`

, `[_]`

, `[_, _]`

, ..., and the function would never become exhaustive. However, it is possible to force a finite game by choosing a pattern which matches a cofinite number of values.

Try it and let me know what you think!