Pattern matching

Pattern matching is a language construct for conditional execution and value retrieval based on structure of data in functional programming languages such as Mathematica, Haskell and ML. It is not as complex as common string pattern matching features such as regular expressions, instead it is built to the core of the language as a general tool even for tree-like data. Depending on the languages, pattern matching can be used for function arguments, in case expressions, whenever new variables are bound, or in very limited situations such as only for sequences in assignment in Python. Often it is possible to give alternative patterns that are tried one by one. Pattern matching leaves room for expression conditionals in form of pattern guards.

The simplest pattern to match is a single value or variable. Consider a simple Haskell function definition (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. Haskell supports alternative patterns in function definitions, so we can continue the definition:

f n = n * f (n-1)

Here, the first n is a single variable pattern. It always matches as any argument can be bound to name n. In Haskell (unlike at least Hope), patterns are tried in order so f 0 is still one. For any other argument the function returns n * f (n-1) with n being the argument.

Wildcard pattern (often written as _) is also simple: it matches any value and the value is not bound to any name.

More complex patterns can be built from these simple ones, usually in the same way as values are built by combining other values. With certain data types implemented in these programming languages, such as a list, the construction of these types form a very definite structure. For example a list is defined as an element constructed on to an empty list, or an element constructed on a list. In Haskell syntax:

a:[]    -- element constructed on an empty list
a:[a,a] -- element constructed on a list

The structure 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:

head (element:list) = element

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:

head (element:_) = element

Pattern matching is not limited to mere lists, but to user-defined data types. In Haskell, the following code segment defines a data type Color that associates an integer with a string.

 data Color = ColorConstructor Integer String

The keyword ColorConstructor is merely a tag to associate the different data types together. It is similar to a C struct.

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? Such programming languages aforementioned use pattern matching to do so. For example, for a function to get the integer part of Color, we can write:

  integerPart (ColorConstructor theInteger _) = theInteger

Or conversely:

  stringPart (ColorConstructor _ theString) = theString

See also

• Pattern recognition for fuzzy patterns
• Category:Pattern matching for articles about string pattern matching
• AIML for an AI language based on matching patterns in speech

External links

• A Gentle Introduction to Haskell: Patterns

• Views: An Extension to Haskell Pattern Matching

References

• The Haskell 98 Report, chapter 3.17 Pattern Matching.

• Pattern matching in The Free On-line Dictionary of Computing, Editor Denis Howe.

• Python Reference Manual, chapter 6.3 Assignment statements.