Previous Up

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, Sn 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 S4:
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 Bn as a matrix whose only non-wildcard patterns are the diagonal.
bii = B,    bji = _ otherwise
Then, Vn 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 V3:
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. Tn 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 T4:
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.

Previous Up