Functorial Blog

A blog about functional programming

RSS Feed

© Phil Freeman 2010-2017

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!