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.