Pattern matching

I've long had a vague idea of what pattern matching is, but never really appreciated why it is a desirable feature in programming languages. We recently covered the topic of pattern matching in the Functional Programming Principles in Scala course I'm taking, and I feel that I now have a much better understanding of it.

The C2 wiki's page on pattern matching contains a much better description than Wikipedia's, which is to be expected for such technical topics. In short,

Pattern matching is the compiler's ability to compare both the form and the content of two expressions.

It is a dispatch mechanism for choosing which variant of a function to call based on the form and content of its argument(s).

The value of pattern matching is in making programming more declarative and logical. Declarative programming lets the programmer to focus on the what instead of the how. This allows programming at a higher level and focusing more on the problem domain, which should increase the odds that the program is correct.

Coming from Clojure, I can best understand pattern matching as a combination of two familiar concepts:

• case expressions
• Destructuring

In languages without pattern matching, it is necessary to explicitly check the form and content of inputs, which leads to a lot of boilerplate.

Consider the following implementation of flatten in Scheme:

(define (flatten x)
  (cond ((null? x) '())
        ((pair? x) (append (flatten (car x)) (flatten (cdr x))))
        (else (list x))))

Here, we have to explicitly use a cond on x to decide what to do.

In Scala, the solution is more declarative, and therefore easier to read and understand:

def flatten(xs: List[Any]): List[Any] = xs match {
  case List() => List()
  case (y :: ys) :: yss => flatten(y :: ys) ::: flatten(yss)
  case y :: ys => y :: flatten(ys)
}

In fact, Philip Wadler wrote a whole critique of SICP, and lack of pattern matching is the first issue he raises (along with non-mathematical synatx, lack of static and user-defined types, and lack of lazy evaluation). For more, see a critique of the critique by Leonardo Borges using Clojure and Haskell.

Clojure supports pattern matching through a library, core.match. As a dispatching mechanism, however, pattern matching seems to be less idiomatic than multimethods. Multimethods allow dispatching on arguments based on an arbitrary dispatching function, which is even more general than pattern matching; however, it is less concise and, in my opinion, less elegant.