A  Series of examples

Series I

This series is simple matching by n constant constructors: For a given integer n:

type t = A0 | A1 | ⋯ | An−1

let f = function
| A0 -> 0
| A1 -> 1
     ⋯
| An−1 -> n−1

Series S

This series, taken from Sestoft [1996], is a variation of matching by a diagonal matrix. For a given integer n, S_n is a (n+1) × 2n matrix P with, for all i in [1…n]:

s2ii = s2i−1i = A,    sji = _ otherwise.

And:

s2k+1n+1 = A,    s2kn+1 = B.

For instance, here is S₄:

type t = A | B

let f = function
| A,A,_,_,_,_,_,_ -> 1
| _,_,A,A,_,_,_,_ -> 2
| _,_,_,_,A,A,_,_ -> 3
| _,_,_,_,_,_,A,A -> 4
| A,B,A,B,A,B,A,B -> 5

Series V

This series is taken from Sekar et al. [1992], Maranget [1992]. It is best defined inductively. We first define B_n as a matrix whose only non-wildcard patterns are the diagonal.

bii = B,    bji = _ otherwise

Then, V_n is the (n+1) × n(n+1)/2 matrix defined as follows.

V1 =

⎛ ⎜ ⎝

A  B

⎞ ⎟ ⎠

,   Vn =

⎛ ⎜ ⎜ ⎝

A A…A    _ _ …_     Bn   Vn−1

⎞ ⎟ ⎟ ⎠

For instance, here is V₃:

type t = A | B

let f = function
 | A,A,A,_,_,_ -> 1
 | B,_,_,A,A,_ -> 2
 | _,B,_,B,_,A -> 3
 | _,_,B,_,B,B -> 4

This series is a real challenge to pattern matching compilers, especially to those that target decision trees: whatever column is selected, compilation will produce code of exponential size.

Series T

This series is made of triangular matrices. T_n is the 2n × n matrix defined as follows.

tj2k+1 = _ (when j < 2k+1),   tj2k+1 = A (otherwise) tj2k = _ (when j < 2k),   tj2k = B (otherwise)

For instance, here is T₄:

type t = A | B

let f = function 
| A,A,A,A -> 1
| B,B,B,B -> 1
| _,A,A,A -> 2
| _,B,B,B -> 2
| _,_,A,A -> 3
| _,_,B,B -> 3
| _,_,_,A -> 4
| _,_,_,B -> 4

This series yields exponential behavior of naive compilation (along first column) to decisions trees.