Patterns occur in several syntactic contexts in Timber (e.g. in the left hand sides of bindings, lambda expressions and case alternatives). Syntactically, patterns form a subset of expressions; a pattern is one of the following:

- A variable.
- A literal.
- A constructor, possibly applied to a sequence of patterns. The sugered forms for lists and tuples are allowed.
- A fully or incompletely defined struct expression (but not a layout-sensitive struct expression), where the right hand sides of all fields are patterns.
- A pattern in parentheses.

At run-time, patterns are matched against values. Pattern-matching may succeed or fail; in the former case the result is a binding of the variables in the pattern to values. The rules are as follows:

- Matching a variable
*x*against a value*v*always succeeds, binding*x*to*v*. - Binding a literal
*l*against a value*v*succeeds only if the*v*is the value denoted by*l*; no variable is bound. - Matching a constructor pattern
*C p1 ... pn*against a value*v*succeeds only if*v = C v1 ... vn*and matching*pi*against*vi*succeeds for all i; the resulting binding is the union of the bindings resulting from each of these matchings. - Matching a struct pattern against a value
*v*starts by stuffing the record; it then has the form*S {sel1 = p1, ... seln = pn}*. Matching against a value*v*succeeds if*v = S {sel1 = v1, seln = vn}*and matching*pi*against*vi*succeeds for all i; the resulting binding is the union of the bindings resulting from each of these matchings. - Matching (
*p*) against a value is the same as matching*p*against the same value.

The special "wildcard" variable `_` may be used in patterns; in contrast to other variables, it is not bound
by pattern-matching.

A consequence of the way pattern-matching is done is that patterns must be linear; no variable may occur more than once in a pattern.

Syntactically, bindings are divided into type signatures and equations. Equations are either function bindings, pattern bindings or instance bindings for type classes.

- Type signatures.
*var*(,*var*)* ::*qtype**qtype*is a (possibly qualified) type.Examples `x, y, z :: Int``map :: (a -> b) -> [a] -> [b]``elem :: a -> [a] -> Bool \\ Eq a` - Function bindings.
We present first the simplest form of function definition, a sequence of equations, and then how these may be extended with where-clauses and with guards; these extensions may be combined.

- Simple function bindings. A simple function binding is a sequence of equations in layout-sensitive syntax, where
each equation has the form
*var**pat** =*expr*The variable (the name of the function) and the number of patterns must be the same in all equations. The order of equations is significant; when applying the function, pattern-matching is tried starting wih the first equation until it succeeds; the function value is computed from right hand side of that equation, using the variable bindings obtained. Within one equation, patterns are matched from left to right.

Example `zip (x:xs) (y:ys) = (x,y) : zip xs ys``zip _ _ = []` - Bindings with
`where`-clauses.A binding may have attached a

-clause with a list of local bindings in layout-sensitive syntax**where***var**pat** =*expr***where***bind*+Example `formatLine n xs = concatMap f xs`**where**f x = rJust n (show x) - Guarded equations. In addition to patterns, the left hand side may include one or more guards
*var**pat** ( | (*qual*)+ =*expr*)+In the most common case, a

*qual*is a Boolean expression. After pattern-matching has succeeded, the guards are evaluated in turn; the right hand side corresponding to the first true guard (if any) is used.Example `lookup x [] = Nothing``lookup x ((a,b) : xs)``| x == a = Just b``| True = lookup x xs`More complicated guards that bind variables are possible, but omitted here.

- Simple function bindings. A simple function binding is a sequence of equations in layout-sensitive syntax, where
each equation has the form
- Pattern bindings.
*pat*=*expr*where

*pat*is not a variable (in which case the binding is, perhaps counter-intuitively, a function binding).Pattern bindings bind the variables in

*pat*by pattern-matching against the value of*expr*. A pattern binding may not occur as a top-level declaration, but only as a local binding.Example `lookup' x ps = y`**where**Just y = lookup x psThe pattern-binding in the

`where`-clause will fail (and the function application give a run-time error), if the result of calling`lookup`is`Nothing`. - Instance bindings for struct types declared as type classes.

The type signature of an instance of a type class is prepended by the keyword**instance***var*`::`*type**var*=*expr*. For instances, a type signature is compulsory; it is not sufficient to give only the binding defining the instance.**instance**This basic form is to emphasise that an instance is just a struct value that is declared to be used as implicit argument, inserted by the compliler. Two alternative syntactic forms are also available:

- An instance declaration combined with a binding of the typed variable:
**instance***var*`::`*type*=*expr* - An instance declaration where the struct value is specified by a list of bindings:
**instance***var*`::`*type***where***bind+*

- An instance declaration combined with a binding of the typed variable:

With the exception of struct expressions and the second alternative form for instances (which is immediately desugared to a form with a struct expression), bindings in a sequence are mutually recursive. This amounts to bound variables of all types and is independent of whether the corresponding right-hand sides need further evaluation or not.

Evaluation
of bindings takes place in dependency order, but follows the declared order for bindings that are
truly mutually dependent. This declared order is significant for one specific reason: evaluation
of each binding must be able to complete without looking into the actual value of any of its
*forward references*. Failure to do so will result in a run-time error.

Examples | Comments |
---|---|

f 0 = 1 | |

f n = n * f (n-1) | Ordinary recursive function binding |

g h 0 = 1 | |

g h n = n * h (n-1) | Non-recursive higher-order function binding |

f' = g f' | Recursive binding of f' (equivalent to f) |

x = 1 : y | Legal forward reference |

y = 2 : x | Ok, both x and y are cyclic lists |

a = 1 : b | |

b = head a : [] | Legal backward reference (ok to look into the value of a) |

a' = head b' : [] | Illegal forward reference (must look into the value of b') |

b' = 2 : a' | Not reached (run-time error on previous line) |

In addition, binding sequences are subject to the following syntactic restrictions:

- All the equations that make up a function binding must be adjacent to each other with no other binding intervening.
- A type signature must precede the binding equations for the variables that are typed by the signature.