Editing Pattern matching (section)

==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):

<syntaxhighlight lang="haskell">
f 0 = 1
</syntaxhighlight>

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:

<syntaxhighlight lang="haskell">
f n = n * f (n-1)
</syntaxhighlight>

Here, the first <code>n</code> 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 (programming language)|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 <code>n * f (n-1)</code> with n being the argument.

The wildcard pattern (often written as <code>_</code>) 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 [[recursion|recursive]] and non-recursive varieties.<ref>{{cite web| last=Cantatore| first=Alessandro| title=Wildcard matching algorithms| year=2003| url=http://xoomer.virgilio.it/acantato/dev/wildcard/wildmatch.html}}</ref>

===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 type]]s.

====Haskell====
In Haskell, the following line defines an algebraic data type <code>Color</code> that has a single data constructor <code>ColorConstructor</code> that wraps an integer and a string.

<syntaxhighlight lang="haskell">
data Color = ColorConstructor Integer String
</syntaxhighlight>

The constructor is a node in a tree and the integer and string are leaves in branches.

When we want to write [[function (programming)|functions]] to make <code>Color</code> an [[abstract data type]], we wish to write functions to [[Interface (computer science)|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 <code>Color</code>.

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 <code>Color</code>, we can use a simple tree pattern and write:

<syntaxhighlight lang="haskell">
integerPart (ColorConstructor theInteger _) = theInteger
</syntaxhighlight>

As well:
<syntaxhighlight lang="haskell">
stringPart (ColorConstructor _ theString) = theString
</syntaxhighlight>

The creations of these functions can be automated by Haskell's data [[Record (computer science)|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.

<syntaxhighlight lang="ocaml">
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 *)
</syntaxhighlight>