Pattern Matching

Pattern matching is the most fundamental thing - this is how DNA is translated and proteins (which are data-structures) and enzymes (which are procedures) are being made out of the same set of molecules (psychical structures). Or, to be precise, some proteins are enzymes. Some data is code, and code is data.

The machinery of life does not have any numbers. It has a set of unique molecular structures instead, on which it performs pattern matching to find an exact match.

Pattern-matching on a data-structures

Pattern matching is a mechanism for checking a structured/compound value against a pattern. Values could be pattern-matched against possible types too (not just a certain structure).

Just imagine that, like in Lisps, a certain unique type-tag is attached to a value. (Life works exactly this way by attaching primers to "datums").

A successful match is usually combined with implicit destructuring - to establish a separate bindings to the parts (of a structured/compound value).

Matching head and tail of a list structure.

head         :: [a] -> a
head (x:_)   =  x
head []      =  errorEmptyList "head"

tail         :: [a] -> [a]
tail (_:xs)  =  xs
tail []      =  errorEmptyList "tail"

This is even more remarkable - this traverses a structure until it found an exact match. This is exactly how an enzyme may traverse a strand of RNA for a specific match.

last         :: [a] -> a
last [x]     =  x
last (_:xs)  =  last xs
last []      =  errorEmptyList "last"

The filter function on a list structure using list comprehensions.

filter p xs  =  [ x | x <- xs, p x]

filter(P, []) -> [];
filter(P, [H|T]) -> filter(P(H), H, P, T).

filter(true, H, P, T) -> [H|filter(P, T)];
filter(false, H, P, T) -> filter(P, T).

Pattern-matching on type-constructors

Pattern matching is a very powerful technique. It is one of the core concepts upon which languages such as StandardML, Haskell or Erlang has been built.

It combines the notions of ensuring a compound data being of the same type or having the same "shape" and creating new local bindings for the pieces upon a successful match, in a single complex expression.

Standard ML

The case expression is specialized expression for pattern-matching.

fun sum_triple t
    case t of
         (x, y, z) => x + y + z

This is a single-line case expression - a "poor style". Case expressions is intended for exhaustive matching of so-called one-of-type values, like built-in List type.

fun sum (xs) =
    case xs of
      | []     => 0
      | x::xs' => x + sum xs'

But val - the binding construct is really uses implicit pattern-matching.

fun sum_triple t
    let val (x, y, z) = t
    in
        x + y + z
    end 

A function's argument (an actual value) is being pattern-matched against the pattern in a function's parameter, such that local bindings could be created upon a successful match.

fun sum_triple (x, y, z) =
    x + y + z

All functions of Standard ML are taking exactly one argument, not zero, not two. What looks like a more than one argument, it is just a single n-touple.

Type-checker will ensure at compile-time that function's arity and "types of the arguments" are correct by ensuring that the type of a n-touple which is being passed is the same.

This is how we could pass and return multiple values within a single touple

fun rotate_left (x, y, z) = (z, y, x)

And then do something like

- sum_triple (rotate_left (3,4,5));
val it = 12 : int

Patterns, like expressions, could be nested.

Pattern-matching against a 3-n touple of non-empty lists, creating 6 local bindings upon success

exception ListLengthMismatch

fun zip3 args =
    case args of
        ([],[],[]) => []
      | (hd1::tl1, hd2::tl2, hd3::tl3) => (hd1,hd2,hd3) :: zip3 (tl1,tl2,tl3)
      | _ => raise ListLengthMismatch

Pattern-matching a list for "head" and "tail" and the head to be a 3-n touple

fun unzip3 args =
    case args of
        [] => ([],[],[])
      | (a,b,c)::tl => let val (l1,l2,l3) = unzip tl
                       in
                           (a::l1,b::l2,c::l3)
                       end

It is also possible to pattern-match on a multiple clauses of a function.

fun factorial 0 = 1
  | factorial n = n * factorial (n - 1)

Haskell

Erlang

Pattern matching is the core of Erlang language - variables are bound to values through the pattern matching mechanism.

In a pattern matching, a left-hand side pattern is matched against a right-hand side term. If the matching succeeds, any unbound variables in the pattern become bound. If the matching fails, a run-time error occurs.

1> X.
** 1: variable 'X' is unbound **
2> X = 2.
2
3> X + 1.
3

The = operator is NOT assignment, it is the match operator which perform an implicit bindings upon a successful match.