Understanding the algorithm

core.match employs the algorithm described in Luc Maranget's paper [Compiling Pattern Matching to good Decision Trees]((http://www.cs.tufts.edu/~nr/cs257/archive/luc-maranget/jun08.pdf). What follows is a slower paced description of the algorithm.

Consider the following pattern match:

(let [x true
      y true
      z true]
  (match [x y z]
    [_ false true] 1
    [false true _ ] 2
    [_ _ false] 3
    [_ _ true] 4
    :else 5))

It's clear that the above expression will return 4, as the values match the fourth clause.

As a visual add we will show the pattern matrix as it goes through a series of transformations in the following form:

 x y z
-------
[_ f t] 1
[f t _] 2
[_ _ f] 3
[_ _ t] 4
[_ _ _] 5

Note that we've replaced true with t and false with f. Note that the final line is represented as a line of wildcards. Finally we label the columns with the variables (in this context we will use the word "occurrence") and the rows.

Maranget's algorithm is based on a surprisingly simple insight. The semantics of pattern matching dictate that we evaluate the clauses one at a time from top to bottom. Each clause itself is evaluated left to right. Even so this gives us a surprising amount of leeway because of wildcards.

Observe that for the first line to succeed we need never consider x.