GeezerVison

While some concepts are relatively common to many pattern languages, other pattern languages include unique or unusual extensions.

Binding

A way of associating a name with a portion of the scrutinee, so that the name is bound to that portion when the continuation executes. For example, in Rust, match v { (a, b) => ... } expects v to be a pair, and a and b are bindings bringing variables of the same name into scope in the continuation ("...").

Wildcard

Often written as a single underscore, _, the wildcard pattern accepts all values without examining them further, ignoring their structure. Also known as discard, the wild pattern, the catch-all pattern, or as a hole.

Guard

A guard is an expression that must succeed (or yield Boolean true) as a final step before considering a pattern to have successfully matched. In some languages (e.g. Erlang), guards are written using a restricted subset of the full language; in others (e.g. Haskell), guards may use the full language.

Predicate

Some pattern languages allow user-defined predicate functions to be embedded in a pattern. The predicate is applied to the portion of the scrutinee corresponding to the position of the predicate in the pattern; if the predicate responds with Boolean false, the pattern is considered to have failed. For example, in Racket, the pattern (list (? even?) ...) first expects a list, and then applies the predicate even? to each element; the overall pattern thus succeeds only when the scrutinee is a list of even numbers.

View pattern

Languages like Haskell^[16] and Racket^[17] include view patterns, where a user-defined function transforms the portion of the scrutinee corresponding to the position of the view pattern before continuing the match. View patterns generalize predicate patterns, allowing further matching on the result of the function rather than simply expecting a Boolean value.

Constraint

Some pattern languages allow direct comparison of portions of the scrutinee with previously-computed (or constant) data structures. For example, the pattern (== expr) in Racket compares the value against the result of evaluating expr. In Erlang, mention of any variable already in scope in a pattern causes it to act as a constraint in this way (instead of as a binding).

Literal pattern; atomic pattern

Patterns that match simple atomic data such as 123 or "hello" are called literal patterns.

Compound pattern

Patterns that destructure compound values such as lists, hash tables, tuples, structures or records, with sub-patterns for each of the values making up the compound data structure, are called compound patterns.

Alternative (or-pattern)

Many languages allow multiple alternatives at the top-level of a pattern matching construct, each associated with a continuation; some languages allow alternatives within a pattern. In most cases, such alternatives have additional constraints placed on them: for example, every alternative may be required to produce the same set of bindings (at the same types).

Macros

Some languages allow macros in pattern context to allow abstraction over patterns. For example, in Racket, match expanders perform this role.^[18]

The simplest pattern in pattern matching is an explicit value or a variable. For an example, consider a simple function definition in Haskell syntax (function parameters are not in parentheses but are separated by spaces, = is not assignment but definition):

f 0 = 1

Here, 0 is a single value pattern. Now, whenever f is given 0 as argument the pattern matches and the function returns 1. With any other argument, the matching and thus the function fail. As the syntax supports alternative patterns in function definitions, we can continue the definition extending it to take more generic arguments:

f n = n * f (n-1)

Here, the first n is a single variable pattern, which will match absolutely any argument and bind it to name n to be used in the rest of the definition. In Haskell (unlike at least Hope), patterns are tried in order so the first definition still applies in the very specific case of the input being 0, while for any other argument the function returns n * f (n-1) with n being the argument.

The wildcard pattern (often written as _) is also simple: like a variable name, it matches any value, but does not bind the value to any name. Algorithms for matching wildcards in simple string-matching situations have been developed in a number of recursive and non-recursive varieties.^[19]

More complex patterns can be built from the primitive ones of the previous section, usually in the same way as values are built by combining other values. The difference then is that with variable and wildcard parts, a pattern does not build into a single value, but matches a group of values that are the combination of the concrete elements and the elements that are allowed to vary within the structure of the pattern.

A tree pattern describes a part of a tree by starting with a node and specifying some branches and nodes and leaving some unspecified with a variable or wildcard pattern. It may help to think of the abstract syntax tree of a programming language and algebraic data types.

data Color = ColorConstructor Integer String

integerPart (ColorConstructor theInteger _) = theInteger

stringPart (ColorConstructor _ theString) = theString

type color = Red | Black
type 'a tree = Empty | Tree of color * 'a tree * 'a * 'a tree

let rebalance t = match t with
    | Tree (Black, Tree (Red, Tree (Red, a, x, b), y, c), z, d)
    | Tree (Black, Tree (Red, a, x, Tree (Red, b, y, c)), z, d)                                  
    | Tree (Black, a, x, Tree (Red, Tree (Red, b, y, c), z, d))
    | Tree (Black, a, x, Tree (Red, b, y, Tree (Red, c, z, d)))
        ->  Tree (Red, Tree (Black, a, x, b), y, Tree (Black, c, z, d))
    | _ -> t (* the 'catch-all' case if no previous pattern matches *)

Pattern matching can be used to filter data of a certain structure. For instance, in Haskell a list comprehension could be used for this kind of filtering:

[A x|A x <- [A 1, B 1, A 2, B 2]]

evaluates to

[A 1, A 2]

In Mathematica, the only structure that exists is the tree, which is populated by symbols. In the Haskell syntax used thus far, this could be defined as

data SymbolTree = Symbol String [SymbolTree]

An example tree could then look like

Symbol "a" [Symbol "b" [], Symbol "c" []]

In the traditional, more suitable syntax, the symbols are written as they are and the levels of the tree are represented using [], so that for instance a[b,c] is a tree with a as the parent, and b and c as the children.

A pattern in Mathematica involves putting "_" at positions in that tree. For instance, the pattern

A[_]

will match elements such as A[1], A[2], or more generally A[x] where x is any entity. In this case, A is the concrete element, while _ denotes the piece of tree that can be varied. A symbol prepended to _ binds the match to that variable name while a symbol appended to _ restricts the matches to nodes of that symbol. Note that even blanks themselves are internally represented as Blank[] for _ and Blank[x] for _x.

The Mathematica function Cases filters elements of the first argument that match the pattern in the second argument:^[20]

Cases[{a[1], b[1], a[2], b[2]}, a[_] ]

evaluates to

{a[1], a[2]}

Pattern matching applies to the structure of expressions. In the example below,

Cases[ {a[b], a[b, c], a[b[c], d], a[b[c], d[e]], a[b[c], d, e]}, a[b[_], _] ]

returns

{a[b[c],d], a[b[c],d[e]]}

because only these elements will match the pattern a[b[_],_] above.

In Mathematica, it is also possible to extract structures as they are created in the course of computation, regardless of how or where they appear. The function Trace can be used to monitor a computation, and return the elements that arise which match a pattern. For example, we can define the Fibonacci sequence as

fib[0|1]:=1
fib[n_]:= fib[n-1] + fib[n-2]

Then, we can ask the question: Given fib[3], what is the sequence of recursive Fibonacci calls?

Trace[fib[3], fib[_]]

returns a structure that represents the occurrences of the pattern fib[_] in the computational structure:

{fib[3],{fib[2],{fib[1]},{fib[0]}},{fib[1]}}

com[i_] := Binomial[2i, i]
Compile[{x, {i, _Integer}}, x^com[i], {{com[_],  Integer}}]

By far the most common form of pattern matching involves strings of characters. In many programming languages, a particular syntax of strings is used to represent regular expressions, which are patterns describing string characters.

However, it is possible to perform some string pattern matching within the same framework that has been discussed throughout this article.

[] -- an empty list
x:xs -- an element x constructed on a list xs

head (element:list) = element

head (element:_) = element

head[element, ]:=element

StringExpression["a",_]

['a', _]

StringExpression[LetterCharacter, DigitCharacter]

[letter, digit] | isAlpha letter && isDigit digit