Patterns and bindings

Patterns and pattern matching

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.

Bindings

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
    

  Here a 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 where-clause with a list of local bindings in layout-sensitive syntax

    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.

• 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 ps

  The 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.

  instance var :: type
  var = expr
  

  The type signature of an instance of a type class is prepended by the keyword instance. For instances, a type signature is compulsory; it is not sufficient to give only the binding defining the 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+
    

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.