Pattern matching
Functional programming construct
- 19 min read
- 4 chapters
- 1 lab on Lably
Learn it on Lably
Sequence patterns (e.g., a text string) are often described using regular expressions and matched using techniques such as backtracking.
Tree patterns are used in some programming languages as a general tool to process data based on its structure, e.g. C#, F#, Haskell, Java, ML, Python, Racket, Ruby, Rust, Scala, Swift and the symbolic mathematics language Mathematica have special syntax for expressing tree patterns and a language construct for conditional execution and value retrieval based on it.
Often it is possible to give alternative patterns that are tried one by one, which yields a powerful conditional programming construct. Pattern matching sometimes includes support for guards.
History
Early programming languages with pattern matching constructs include COMIT (1957), SNOBOL (1962), which introduced pattern matching as a core, first-class language capability for string and text manipulation. This paradigm evolved into structured, tree-based data evaluation with Refal (1968), which used pattern matching to manipulate symbolic expressions. The concept was soon adapted into logic programming with Prolog (1972), where pattern matching took the form of structural unification to resolve logical queries. Functional programming languages rapidly adopted and formalized the feature across the late 1970s and early 1980s, beginning with the St Andrews Static Language (SASL) (1976), NPL (1977), and the Kent Recursive Calculator (KRC) (1981).
The pattern matching feature of function arguments in the language ML (1973) and its dialect Standard ML (1983) heavily formalized compile-time exhaustiveness checking. This approach has been carried over to some other functional programming languages that were influenced by them, such as Haskell (1990), Scala (2004), and F# (2005). The pattern matching construct with the match keyword that was introduced in the ML dialect Caml (1985) was followed by languages such as OCaml (1996), F# (2005), F* (2011), and Rust (2015). Over time, multi-paradigm languages begin implementing algebraic data types and pattern matching natively, culminating in modern implementations like Python's match-case syntax (2021) and Java's pattern matching enhancements (2023).
Many text editors support pattern matching of various kinds to facilitate advanced search-and-replace capabilities. The QED editor, designed by Ken Thompson, was a pioneer in supporting regular expression searching. Thompson's implementation of regular expression parsing in QED laid the groundwork for the text search utilities in ed, sed, and grep. Furthermore, some versions of the TECO editor supported advanced matching features, including the logical OR operator in searches.
Computer algebra systems (CAS) generally support pattern matching on algebraic expressions to achieve symbolic simplification and integration. Early systems like Macsyma (1968) used semantic pattern matching to recognize algebraic equivalence; for example, its internal engine could successfully match both 3x2 + 4 and (x + 1)(x + 6) as occurrences of a "quadratic in x" pattern template. Modern computer algebra systems, including Mathematica and Maple, rely heavily on pattern-matching rules to transform user expressions, find analytical solutions to differential equations, and build user-defined simplification frameworks.
Sign in to keep reading
3 more chapters are free with a Lably account.
Terminology
Pattern matching involves specialized terminology.
- Matching
- The act of comparing a scrutinee to a pattern (or collection of patterns), possibly selecting a continuation, extracting bindings, performing a substitution, or any combination of these. Also known as destructuring.
- Pattern
- Syntax describing expected structure in the scrutinee, plus specification of portions of the scrutinee to extract (bindings) or ignore (wildcards). Pattern languages can be rich; see below for terminology denoting specific kinds of pattern.
- Scrutinee
- The value to be examined and matched against a pattern. In most cases, this will be a data structure of some kind, with type dual to the pattern being applied. Also known as the subject value or discriminant.
- Continuation
- In some languages, when multiple alternative patterns are applied to a scrutinee, when one alternative matches, an associated code fragment is executed in an environment extended with the matching pattern's bindings. This code fragment is the continuation associated with the pattern.
- Substitution
- Replacement of a portion of a scrutinee data structure with some computed value. The computation may depend on the replaced portion of the scrutinee as well as on other bindings extracted from the scrutinee.
Terminology of patterns
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) => ... }expectsvto be a pair, andaandbare 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 predicateeven?to each element; the overall pattern thus succeeds only when the scrutinee is a list of even numbers. - View pattern
- Languages like Haskell and Racket 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 evaluatingexpr. 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
123or"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.
Types
Primitive patterns
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):
<span id="mwARw"></span><span class="nf" id="mwAR0">f</span><span class="w" id="mwAR4"> </span><span class="mi" id="mwAR8">0</span><span class="w" id="mwASA"> </span><span class="ow" id="mwASE">=</span><span class="w" id="mwASI"> </span><span class="mi" id="mwASM">1</span>
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:
<span id="mwASc"></span><span class="nf" id="mwASg">f</span><span class="w" id="mwASk"> </span><span class="n" id="mwASo">n</span><span class="w" id="mwASs"> </span><span class="ow" id="mwASw">=</span><span class="w" id="mwAS0"> </span><span class="n" id="mwAS4">n</span><span class="w" id="mwAS8"> </span><span class="o" id="mwATA">*</span><span class="w" id="mwATE"> </span><span class="n" id="mwATI">f</span><span class="w" id="mwATM"> </span><span class="p" id="mwATQ">(</span><span class="n" id="mwATU">n</span><span class="o" id="mwATY">-</span><span class="mi" id="mwATc">1</span><span class="p" id="mwATg">)</span>
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.
Tree patterns
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.
Haskell
In Haskell, the following line defines an algebraic data type Color that has a single data constructor ColorConstructor that wraps an integer and a string.
<span id="mwAVA"></span><span class="kr" id="mwAVE">data</span><span class="w" id="mwAVI"> </span><span class="kt" id="mwAVM">Color</span><span class="w" id="mwAVQ"> </span><span class="ow" id="mwAVU">=</span><span class="w" id="mwAVY"> </span><span class="kt" id="mwAVc">ColorConstructor</span><span class="w" id="mwAVg"> </span><span class="kt" id="mwAVk">Integer</span><span class="w" id="mwAVo"> </span><span class="kt" id="mwAVs">String</span>
The constructor is a node in a tree and the integer and string are leaves in branches.
When we want to write functions to make Color an abstract data type, we wish to write functions to interface with the data type, and thus we want to extract some data from the data type, for example, just the string or just the integer part of Color.
If we pass a variable that is of type Color, how can we get the data out of this variable? For example, for a function to get the integer part of Color, we can use a simple tree pattern and write:
<span id="mwAWc"></span><span class="nf" id="mwAWg">integerPart</span><span class="w" id="mwAWk"> </span><span class="p" id="mwAWo">(</span><span class="kt" id="mwAWs">ColorConstructor</span><span class="w" id="mwAWw"> </span><span class="n" id="mwAW0">theInteger</span><span class="w" id="mwAW4"> </span><span class="kr" id="mwAW8">_</span><span class="p" id="mwAXA">)</span><span class="w" id="mwAXE"> </span><span class="ow" id="mwAXI">=</span><span class="w" id="mwAXM"> </span><span class="n" id="mwAXQ">theInteger</span>
As well:
<span id="mwAXg"></span><span class="nf" id="mwAXk">stringPart</span><span class="w" id="mwAXo"> </span><span class="p" id="mwAXs">(</span><span class="kt" id="mwAXw">ColorConstructor</span><span class="w" id="mwAX0"> </span><span class="kr" id="mwAX4">_</span><span class="w" id="mwAX8"> </span><span class="n" id="mwAYA">theString</span><span class="p" id="mwAYE">)</span><span class="w" id="mwAYI"> </span><span class="ow" id="mwAYM">=</span><span class="w" id="mwAYQ"> </span><span class="n" id="mwAYU">theString</span>
The creations of these functions can be automated by Haskell's data record syntax.
OCaml
This OCaml example which defines a red–black tree and a function to re-balance it after element insertion shows how to match on a more complex structure generated by a recursive data type. The compiler verifies at compile-time that the list of cases is exhaustive and none are redundant.
<span id="mwAY4"></span><span class="k" id="mwAY8">type</span> <span class="n" id="mwAZA">color</span> <span class="o" id="mwAZE">=</span> <span class="nc" id="mwAZI">Red</span> <span class="o" id="mwAZM">|</span> <span class="nc" id="mwAZQ">Black</span> <span class="k" id="mwAZU">type</span> <span class="k" id="mwAZY">'</span><span class="n" id="mwAZc">a</span> <span class="n" id="mwAZg">tree</span> <span class="o" id="mwAZk">=</span> <span class="nc" id="mwAZo">Empty</span> <span class="o" id="mwAZs">|</span> <span class="nc" id="mwAZw">Tree</span> <span class="k" id="mwAZ0">of</span> <span class="n" id="mwAZ4">color</span> <span class="o" id="mwAZ8">*</span> <span class="k" id="mwAaA">'</span><span class="n" id="mwAaE">a</span> <span class="n" id="mwAaI">tree</span> <span class="o" id="mwAaM">*</span> <span class="k" id="mwAaQ">'</span><span class="n" id="mwAaU">a</span> <span class="o" id="mwAaY">*</span> <span class="k" id="mwAac">'</span><span class="n" id="mwAag">a</span> <span class="n" id="mwAak">tree</span> <span class="k" id="mwAao">let</span> <span class="n" id="mwAas">rebalance</span> <span class="n" id="mwAaw">t</span> <span class="o" id="mwAa0">=</span> <span class="k" id="mwAa4">match</span> <span class="n" id="mwAa8">t</span> <span class="k" id="mwAbA">with</span> <span class="o" id="mwAbE">|</span> <span class="nc" id="mwAbI">Tree</span> <span class="o" id="mwAbM">(</span><span class="nc" id="mwAbQ">Black</span><span class="o" id="mwAbU">,</span> <span class="nc" id="mwAbY">Tree</span> <span class="o" id="mwAbc">(</span><span class="nc" id="mwAbg">Red</span><span class="o" id="mwAbk">,</span> <span class="nc" id="mwAbo">Tree</span> <span class="o" id="mwAbs">(</span><span class="nc" id="mwAbw">Red</span><span class="o" id="mwAb0">,</span> <span class="n" id="mwAb4">a</span><span class="o" id="mwAb8">,</span> <span class="n" id="mwAcA">x</span><span class="o" id="mwAcE">,</span> <span class="n" id="mwAcI">b</span><span class="o" id="mwAcM">),</span> <span class="n" id="mwAcQ">y</span><span class="o" id="mwAcU">,</span> <span class="n" id="mwAcY">c</span><span class="o" id="mwAcc">),</span> <span class="n" id="mwAcg">z</span><span class="o" id="mwAck">,</span> <span class="n" id="mwAco">d</span><span class="o" id="mwAcs">)</span> <span class="o" id="mwAcw">|</span> <span class="nc" id="mwAc0">Tree</span> <span class="o" id="mwAc4">(</span><span class="nc" id="mwAc8">Black</span><span class="o" id="mwAdA">,</span> <span class="nc" id="mwAdE">Tree</span> <span class="o" id="mwAdI">(</span><span class="nc" id="mwAdM">Red</span><span class="o" id="mwAdQ">,</span> <span class="n" id="mwAdU">a</span><span class="o" id="mwAdY">,</span> <span class="n" id="mwAdc">x</span><span class="o" id="mwAdg">,</span> <span class="nc" id="mwAdk">Tree</span> <span class="o" id="mwAdo">(</span><span class="nc" id="mwAds">Red</span><span class="o" id="mwAdw">,</span> <span class="n" id="mwAd0">b</span><span class="o" id="mwAd4">,</span> <span class="n" id="mwAd8">y</span><span class="o" id="mwAeA">,</span> <span class="n" id="mwAeE">c</span><span class="o" id="mwAeI">)),</span> <span class="n" id="mwAeM">z</span><span class="o" id="mwAeQ">,</span> <span class="n" id="mwAeU">d</span><span class="o" id="mwAeY">)</span> <span class="o" id="mwAec">|</span> <span class="nc" id="mwAeg">Tree</span> <span class="o" id="mwAek">(</span><span class="nc" id="mwAeo">Black</span><span class="o" id="mwAes">,</span> <span class="n" id="mwAew">a</span><span class="o" id="mwAe0">,</span> <span class="n" id="mwAe4">x</span><span class="o" id="mwAe8">,</span> <span class="nc" id="mwAfA">Tree</span> <span class="o" id="mwAfE">(</span><span class="nc" id="mwAfI">Red</span><span class="o" id="mwAfM">,</span> <span class="nc" id="mwAfQ">Tree</span> <span class="o" id="mwAfU">(</span><span class="nc" id="mwAfY">Red</span><span class="o" id="mwAfc">,</span> <span class="n" id="mwAfg">b</span><span class="o" id="mwAfk">,</span> <span class="n" id="mwAfo">y</span><span class="o" id="mwAfs">,</span> <span class="n" id="mwAfw">c</span><span class="o" id="mwAf0">),</span> <span class="n" id="mwAf4">z</span><span class="o" id="mwAf8">,</span> <span class="n" id="mwAgA">d</span><span class="o" id="mwAgE">))</span> <span class="o" id="mwAgI">|</span> <span class="nc" id="mwAgM">Tree</span> <span class="o" id="mwAgQ">(</span><span class="nc" id="mwAgU">Black</span><span class="o" id="mwAgY">,</span> <span class="n" id="mwAgc">a</span><span class="o" id="mwAgg">,</span> <span class="n" id="mwAgk">x</span><span class="o" id="mwAgo">,</span> <span class="nc" id="mwAgs">Tree</span> <span class="o" id="mwAgw">(</span><span class="nc" id="mwAg0">Red</span><span class="o" id="mwAg4">,</span> <span class="n" id="mwAg8">b</span><span class="o" id="mwAhA">,</span> <span class="n" id="mwAhE">y</span><span class="o" id="mwAhI">,</span> <span class="nc" id="mwAhM">Tree</span> <span class="o" id="mwAhQ">(</span><span class="nc" id="mwAhU">Red</span><span class="o" id="mwAhY">,</span> <span class="n" id="mwAhc">c</span><span class="o" id="mwAhg">,</span> <span class="n" id="mwAhk">z</span><span class="o" id="mwAho">,</span> <span class="n" id="mwAhs">d</span><span class="o" id="mwAhw">)))</span> <span class="o" id="mwAh0">-></span> <span class="nc" id="mwAh4">Tree</span> <span class="o" id="mwAh8">(</span><span class="nc" id="mwAiA">Red</span><span class="o" id="mwAiE">,</span> <span class="nc" id="mwAiI">Tree</span> <span class="o" id="mwAiM">(</span><span class="nc" id="mwAiQ">Black</span><span class="o" id="mwAiU">,</span> <span class="n" id="mwAiY">a</span><span class="o" id="mwAic">,</span> <span class="n" id="mwAig">x</span><span class="o" id="mwAik">,</span> <span class="n" id="mwAio">b</span><span class="o" id="mwAis">),</span> <span class="n" id="mwAiw">y</span><span class="o" id="mwAi0">,</span> <span class="nc" id="mwAi4">Tree</span> <span class="o" id="mwAi8">(</span><span class="nc" id="mwAjA">Black</span><span class="o" id="mwAjE">,</span> <span class="n" id="mwAjI">c</span><span class="o" id="mwAjM">,</span> <span class="n" id="mwAjQ">z</span><span class="o" id="mwAjU">,</span> <span class="n" id="mwAjY">d</span><span class="o" id="mwAjc">))</span> <span class="o" id="mwAjg">|</span> <span class="o" id="mwAjk">_</span> <span class="o" id="mwAjo">-></span> <span class="n" id="mwAjs">t</span> <span class="c" id="mwAjw">(* the 'catch-all' case if no previous pattern matches *)</span>
Usage
Filtering data with patterns
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:
<span id="mwAkM"></span><span class="p" id="mwAkQ">[</span><span class="kt" id="mwAkU">A</span><span class="w" id="mwAkY"> </span><span class="n" id="mwAkc">x</span><span class="o" id="mwAkg">|</span><span class="kt" id="mwAkk">A</span><span class="w" id="mwAko"> </span><span class="n" id="mwAks">x</span><span class="w" id="mwAkw"> </span><span class="ow" id="mwAk0"><-</span><span class="w" id="mwAk4"> </span><span class="p" id="mwAk8">[</span><span class="kt" id="mwAlA">A</span><span class="w" id="mwAlE"> </span><span class="mi" id="mwAlI">1</span><span class="p" id="mwAlM">,</span><span class="w" id="mwAlQ"> </span><span class="kt" id="mwAlU">B</span><span class="w" id="mwAlY"> </span><span class="mi" id="mwAlc">1</span><span class="p" id="mwAlg">,</span><span class="w" id="mwAlk"> </span><span class="kt" id="mwAlo">A</span><span class="w" id="mwAls"> </span><span class="mi" id="mwAlw">2</span><span class="p" id="mwAl0">,</span><span class="w" id="mwAl4"> </span><span class="kt" id="mwAl8">B</span><span class="w" id="mwAmA"> </span><span class="mi" id="mwAmE">2</span><span class="p" id="mwAmI">]]</span>
evaluates to
[A 1, A 2]
Pattern matching in Mathematica
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
<span id="mwAmw"></span><span class="kr" id="mwAm0">data</span><span class="w" id="mwAm4"> </span><span class="kt" id="mwAm8">SymbolTree</span><span class="w" id="mwAnA"> </span><span class="ow" id="mwAnE">=</span><span class="w" id="mwAnI"> </span><span class="kt" id="mwAnM">Symbol</span><span class="w" id="mwAnQ"> </span><span class="kt" id="mwAnU">String</span><span class="w" id="mwAnY"> </span><span class="p" id="mwAnc">[</span><span class="kt" id="mwAng">SymbolTree</span><span class="p" id="mwAnk">]</span>
An example tree could then look like
<span id="mwAn0"></span><span class="n" id="mwAn4">Symbol</span><span class="w" id="mwAn8"> </span><span class="s" id="mwAoA">"a"</span><span class="w" id="mwAoE"> </span><span class="p" id="mwAoI">[</span><span class="n" id="mwAoM">Symbol</span><span class="w" id="mwAoQ"> </span><span class="s" id="mwAoU">"b"</span><span class="w" id="mwAoY"> </span><span class="p" id="mwAoc">[],</span><span class="w" id="mwAog"> </span><span class="n" id="mwAok">Symbol</span><span class="w" id="mwAoo"> </span><span class="s" id="mwAos">"c"</span><span class="w" id="mwAow"> </span><span class="p" id="mwAo0">[]]</span>
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:
<span id="mwAqY"></span><span class="n" id="mwAqc">Cases</span><span class="p" id="mwAqg">[{</span><span class="n" id="mwAqk">a</span><span class="p" id="mwAqo">[</span><span class="mi" id="mwAqs">1</span><span class="p" id="mwAqw">],</span><span class="w" id="mwAq0"> </span><span class="n" id="mwAq4">b</span><span class="p" id="mwAq8">[</span><span class="mi" id="mwArA">1</span><span class="p" id="mwArE">],</span><span class="w" id="mwArI"> </span><span class="n" id="mwArM">a</span><span class="p" id="mwArQ">[</span><span class="mi" id="mwArU">2</span><span class="p" id="mwArY">],</span><span class="w" id="mwArc"> </span><span class="n" id="mwArg">b</span><span class="p" id="mwArk">[</span><span class="mi" id="mwAro">2</span><span class="p" id="mwArs">]},</span><span class="w" id="mwArw"> </span><span class="n" id="mwAr0">a</span><span class="p" id="mwAr4">[</span><span class="nv" id="mwAr8">_</span><span class="p" id="mwAsA">]</span><span class="w" id="mwAsE"> </span><span class="p" id="mwAsI">]</span>evaluates to
<span id="mwAsY"></span><span class="p" id="mwAsc">{</span><span class="n" id="mwAsg">a</span><span class="p" id="mwAsk">[</span><span class="mi" id="mwAso">1</span><span class="p" id="mwAss">],</span><span class="w" id="mwAsw"> </span><span class="n" id="mwAs0">a</span><span class="p" id="mwAs4">[</span><span class="mi" id="mwAs8">2</span><span class="p" id="mwAtA">]}</span>Pattern matching applies to the structure of expressions. In the example below,
<span id="mwAtU"></span><span class="n" id="mwAtY">Cases</span><span class="p" id="mwAtc">[</span><span class="w" id="mwAtg"> </span><span class="p" id="mwAtk">{</span><span class="n" id="mwAto">a</span><span class="p" id="mwAts">[</span><span class="n" id="mwAtw">b</span><span class="p" id="mwAt0">],</span><span class="w" id="mwAt4"> </span><span class="n" id="mwAt8">a</span><span class="p" id="mwAuA">[</span><span class="n" id="mwAuE">b</span><span class="p" id="mwAuI">,</span><span class="w" id="mwAuM"> </span><span class="n" id="mwAuQ">c</span><span class="p" id="mwAuU">],</span><span class="w" id="mwAuY"> </span><span class="n" id="mwAuc">a</span><span class="p" id="mwAug">[</span><span class="n" id="mwAuk">b</span><span class="p" id="mwAuo">[</span><span class="n" id="mwAus">c</span><span class="p" id="mwAuw">],</span><span class="w" id="mwAu0"> </span><span class="n" id="mwAu4">d</span><span class="p" id="mwAu8">],</span><span class="w" id="mwAvA"> </span><span class="n" id="mwAvE">a</span><span class="p" id="mwAvI">[</span><span class="n" id="mwAvM">b</span><span class="p" id="mwAvQ">[</span><span class="n" id="mwAvU">c</span><span class="p" id="mwAvY">],</span><span class="w" id="mwAvc"> </span><span class="n" id="mwAvg">d</span><span class="p" id="mwAvk">[</span><span class="n" id="mwAvo">e</span><span class="p" id="mwAvs">]],</span><span class="w" id="mwAvw"> </span><span class="n" id="mwAv0">a</span><span class="p" id="mwAv4">[</span><span class="n" id="mwAv8">b</span><span class="p" id="mwAwA">[</span><span class="n" id="mwAwE">c</span><span class="p" id="mwAwI">],</span><span class="w" id="mwAwM"> </span><span class="n" id="mwAwQ">d</span><span class="p" id="mwAwU">,</span><span class="w" id="mwAwY"> </span><span class="n" id="mwAwc">e</span><span class="p" id="mwAwg">]},</span><span class="w" id="mwAwk"> </span><span class="n" id="mwAwo">a</span><span class="p" id="mwAws">[</span><span class="n" id="mwAww">b</span><span class="p" id="mwAw0">[</span><span class="nv" id="mwAw4">_</span><span class="p" id="mwAw8">],</span><span class="w" id="mwAxA"> </span><span class="nv" id="mwAxE">_</span><span class="p" id="mwAxI">]</span><span class="w" id="mwAxM"> </span><span class="p" id="mwAxQ">]</span>returns
<span id="mwAxg"></span><span class="p" id="mwAxk">{</span><span class="n" id="mwAxo">a</span><span class="p" id="mwAxs">[</span><span class="n" id="mwAxw">b</span><span class="p" id="mwAx0">[</span><span class="n" id="mwAx4">c</span><span class="p" id="mwAx8">],</span><span class="n" id="mwAyA">d</span><span class="p" id="mwAyE">],</span><span class="w" id="mwAyI"> </span><span class="n" id="mwAyM">a</span><span class="p" id="mwAyQ">[</span><span class="n" id="mwAyU">b</span><span class="p" id="mwAyY">[</span><span class="n" id="mwAyc">c</span><span class="p" id="mwAyg">],</span><span class="n" id="mwAyk">d</span><span class="p" id="mwAyo">[</span><span class="n" id="mwAys">e</span><span class="p" id="mwAyw">]]}</span>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
<span id="mwAzQ"></span><span class="n" id="mwAzU">fib</span><span class="p" id="mwAzY">[</span><span class="mi" id="mwAzc">0</span><span class="o" id="mwAzg">|</span><span class="mi" id="mwAzk">1</span><span class="p" id="mwAzo">]</span><span class="o" id="mwAzs">:=</span><span class="mi" id="mwAzw">1</span> <span class="n" id="mwAz0">fib</span><span class="p" id="mwAz4">[</span><span class="nv" id="mwAz8">n_</span><span class="p" id="mwA0A">]</span><span class="o" id="mwA0E">:=</span><span class="w" id="mwA0I"> </span><span class="n" id="mwA0M">fib</span><span class="p" id="mwA0Q">[</span><span class="n" id="mwA0U">n</span><span class="mi" id="mwA0Y">-1</span><span class="p" id="mwA0c">]</span><span class="w" id="mwA0g"> </span><span class="o" id="mwA0k">+</span><span class="w" id="mwA0o"> </span><span class="n" id="mwA0s">fib</span><span class="p" id="mwA0w">[</span><span class="n" id="mwA00">n</span><span class="mi" id="mwA04">-2</span><span class="p" id="mwA08">]</span>
Then, we can ask the question: Given fib[3], what is the sequence of recursive Fibonacci calls?
<span id="mwA1M"></span><span class="n" id="mwA1Q">Trace</span><span class="p" id="mwA1U">[</span><span class="n" id="mwA1Y">fib</span><span class="p" id="mwA1c">[</span><span class="mi" id="mwA1g">3</span><span class="p" id="mwA1k">],</span><span class="w" id="mwA1o"> </span><span class="n" id="mwA1s">fib</span><span class="p" id="mwA1w">[</span><span class="nv" id="mwA10">_</span><span class="p" id="mwA14">]]</span>
returns a structure that represents the occurrences of the pattern fib[_] in the computational structure:
<span id="mwA2M"></span><span class="p" id="mwA2Q">{</span><span class="n" id="mwA2U">fib</span><span class="p" id="mwA2Y">[</span><span class="mi" id="mwA2c">3</span><span class="p" id="mwA2g">],{</span><span class="n" id="mwA2k">fib</span><span class="p" id="mwA2o">[</span><span class="mi" id="mwA2s">2</span><span class="p" id="mwA2w">],{</span><span class="n" id="mwA20">fib</span><span class="p" id="mwA24">[</span><span class="mi" id="mwA28">1</span><span class="p" id="mwA3A">]},{</span><span class="n" id="mwA3E">fib</span><span class="p" id="mwA3I">[</span><span class="mi" id="mwA3M">0</span><span class="p" id="mwA3Q">]}},{</span><span class="n" id="mwA3U">fib</span><span class="p" id="mwA3Y">[</span><span class="mi" id="mwA3c">1</span><span class="p" id="mwA3g">]}}</span>Declarative programming
In symbolic programming languages, it is easy to have patterns as arguments to functions or as elements of data structures. A consequence of this is the ability to use patterns to declaratively make statements about pieces of data and to flexibly instruct functions how to operate.
For instance, the Mathematica function Compile can be used to make more efficient versions of the code. In the following example the details do not particularly matter; what matters is that the subexpression {{com[_], Integer}} instructs Compile that expressions of the form com[_] can be assumed to be integers for the purposes of compilation:
<span id="mwA4Q"></span><span class="n" id="mwA4U">com</span><span class="p" id="mwA4Y">[</span><span class="nv" id="mwA4c">i_</span><span class="p" id="mwA4g">]</span><span class="w" id="mwA4k"> </span><span class="o" id="mwA4o">:=</span><span class="w" id="mwA4s"> </span><span class="n" id="mwA4w">Binomial</span><span class="p" id="mwA40">[</span><span class="mi" id="mwA44">2</span><span class="n" id="mwA48">i</span><span class="p" id="mwA5A">,</span><span class="w" id="mwA5E"> </span><span class="n" id="mwA5I">i</span><span class="p" id="mwA5M">]</span> <span class="n" id="mwA5Q">Compile</span><span class="p" id="mwA5U">[{</span><span class="n" id="mwA5Y">x</span><span class="p" id="mwA5c">,</span><span class="w" id="mwA5g"> </span><span class="p" id="mwA5k">{</span><span class="n" id="mwA5o">i</span><span class="p" id="mwA5s">,</span><span class="w" id="mwA5w"> </span><span class="nv" id="mwA50">_Integer</span><span class="p" id="mwA54">}},</span><span class="w" id="mwA58"> </span><span class="n" id="mwA6A">x</span><span class="o" id="mwA6E">^</span><span class="n" id="mwA6I">com</span><span class="p" id="mwA6M">[</span><span class="n" id="mwA6Q">i</span><span class="p" id="mwA6U">],</span><span class="w" id="mwA6Y"> </span><span class="p" id="mwA6c">{{</span><span class="n" id="mwA6g">com</span><span class="p" id="mwA6k">[</span><span class="nv" id="mwA6o">_</span><span class="p" id="mwA6s">],</span><span class="w" id="mwA6w"> </span><span class="n" id="mwA60">Integer</span><span class="p" id="mwA64">}}]</span>Mailboxes in Erlang also work this way.
The Curry–Howard correspondence between proofs and programs relates ML-style pattern matching to case analysis and proof by exhaustion.
Pattern matching and strings
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.
Tree patterns for strings
In Mathematica, strings are represented as trees of root StringExpression and all the characters in order as children of the root. Thus, to match "any amount of trailing characters", a new wildcard ___ is needed in contrast to _ that would match only a single character.
In Haskell and functional programming languages in general, strings are represented as functional lists of characters. A functional list is defined as an empty list, or an element constructed on an existing list. In Haskell syntax:
<span id="mwA8A"></span><span class="kt" id="mwA8E">[]</span><span class="w" id="mwA8I"> </span><span class="c1" id="mwA8M">-- an empty list</span> <span class="nf" id="mwA8Q">x</span><span class="kt" id="mwA8U">:</span><span class="n" id="mwA8Y">xs</span><span class="w" id="mwA8c"> </span><span class="c1" id="mwA8g">-- an element x constructed on a list xs</span>
The structure for a list with some elements is thus element:list. When pattern matching, we assert that a certain piece of data is equal to a certain pattern. For example, in the function:
<span id="mwA80"></span><span class="nf" id="mwA84">head</span><span class="w" id="mwA88"> </span><span class="p" id="mwA9A">(</span><span class="n" id="mwA9E">element</span><span class="kt" id="mwA9I">:</span><span class="n" id="mwA9M">list</span><span class="p" id="mwA9Q">)</span><span class="w" id="mwA9U"> </span><span class="ow" id="mwA9Y">=</span><span class="w" id="mwA9c"> </span><span class="n" id="mwA9g">element</span>
We assert that the first element of head's argument is called element, and the function returns this. We know that this is the first element because of the way lists are defined, a single element constructed onto a list. This single element must be the first. The empty list would not match the pattern at all, as an empty list does not have a head (the first element that is constructed).
In the example, we have no use for list, so we can disregard it, and thus write the function:
<span id="mwA98"></span><span class="nf" id="mwA-A">head</span><span class="w" id="mwA-E"> </span><span class="p" id="mwA-I">(</span><span class="n" id="mwA-M">element</span><span class="kt" id="mwA-Q">:</span><span class="kr" id="mwA-U">_</span><span class="p" id="mwA-Y">)</span><span class="w" id="mwA-c"> </span><span class="ow" id="mwA-g">=</span><span class="w" id="mwA-k"> </span><span class="n" id="mwA-o">element</span>
The equivalent Mathematica transformation is expressed as
head[element, ]:=element
Example string patterns
In Mathematica, for instance,
<span id="mwA_E"></span><span class="n" id="mwA_I">StringExpression</span><span class="p" id="mwA_M">[</span><span class="s" id="mwA_Q">"a"</span><span class="p" id="mwA_U">,</span><span class="nv" id="mwA_Y">_</span><span class="p" id="mwA_c">]</span>
will match a string that has two characters and begins with "a".
The same pattern in Haskell:
<span id="mwA_w"></span><span class="p" id="mwA_0">[</span><span class="sc" id="mwA_4">'a'</span><span class="p" id="mwA_8">,</span><span class="w" id="mwBAA"> </span><span class="kr" id="mwBAE">_</span><span class="p" id="mwBAI">]</span>
Symbolic entities can be introduced to represent many different classes of relevant features of a string. For instance,
StringExpression[LetterCharacter, DigitCharacter]
will match a string that consists of a letter first, and then a number.
In Haskell, guards could be used to achieve the same matches:
<span id="mwBAo"></span><span class="p" id="mwBAs">[</span><span class="n" id="mwBAw">letter</span><span class="p" id="mwBA0">,</span><span class="w" id="mwBA4"> </span><span class="n" id="mwBA8">digit</span><span class="p" id="mwBBA">]</span><span class="w" id="mwBBE"> </span><span class="o" id="mwBBI">|</span><span class="w" id="mwBBM"> </span><span class="n" id="mwBBQ">isAlpha</span><span class="w" id="mwBBU"> </span><span class="n" id="mwBBY">letter</span><span class="w" id="mwBBc"> </span><span class="o" id="mwBBg">&&</span><span class="w" id="mwBBk"> </span><span class="n" id="mwBBo">isDigit</span><span class="w" id="mwBBs"> </span><span class="n" id="mwBBw">digit</span>
The main advantage of symbolic string manipulation is that it can be completely integrated with the rest of the programming language, rather than being a separate, special purpose subunit. The entire power of the language can be leveraged to build up the patterns themselves or analyze and transform the programs that contain them.
SNOBOL
SNOBOL (StriNg Oriented and symBOlic Language) is a computer programming language developed between 1962 and 1967 at AT&T Bell Laboratories by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky.
SNOBOL4 stands apart from most programming languages by having patterns as a first-class data type (i.e. a data type whose values can be manipulated in all ways permitted to any other data type in the programming language) and by providing operators for pattern concatenation and alternation. Strings generated during execution can be treated as programs and executed.
SNOBOL was quite widely taught in larger US universities in the late 1960s and early 1970s and was widely used in the 1970s and 1980s as a text manipulation language in the humanities.
Since SNOBOL's creation, newer languages such as AWK and Perl have made string manipulation by means of regular expressions fashionable. SNOBOL4 patterns, however, subsume Backus–Naur form (BNF) grammars, which are equivalent to context-free grammars and more powerful than regular expressions.