Department of Computer Science

More about functions

Patterns

Function definitions are written as a sequence of clauses (or equations) each of which provides the answer for one pattern of arguments:

$$\begin{array}{ll} \mbox{\em fname patterns}_{1} & = \mbox{\e... ...mbox{\em fname patterns}_{n} & = \mbox{\em rhs}_{n} \end{array}$$

Patterns consist of constants, variables and data constructors (eg. : or (,..)). A constant only matches itself, a variable matches anything - and gets bound to the value it matched - and a constructor only matches values built from that constructor if the component patterns match.

When a function is applied to an argument the patterns of each clause of the definition are matched, in turn, with the argument. When a match occurs the expression on the right hand side (rhs) is evaluated giving the result of the function. For example:

        iszero 0 = True
        iszero n = False

if iszero is applied to an argument as in:

        iszero 37

it fails to match the first clause because 0 does not equal 37 but the variable ``n'' matches anything so the second clause is used and False is the result. The simple function to exchange the components of a pair tuple:

        exchange (a,b) = (b,a)

The pattern (a,b) only matches pairs, and a and b will match any values, they are bound to the two components of the actual value and then the right hand side reconstructs a pair with the elements reversed.

The next example is a function called front that will return the first element of a list ^5.3. Remember that the empty list: [], is a list so it must be matched but it has no first element:

        front [] = error "empty list to front"
        front (h:t) = h

the pattern [] will only match an empty list and the corresponding right hand side has no result, instead it aborts the program, error is not just an error message. If the list is non-empty it must have been made with ``:'' and the pattern (h:t) will match it binding h to the first element and t to the rest of the list:

        front [1,2,3,4]

is equivalent to:

        front (1 : (2 : (3 : (4 : []))))

and the pattern matches setting:

        h = 1
        t = (2 : (3 : (4 : [])))

Recusion interlude

This is not about functional programming languages it is about functional programming. It is included because not knowing how to write functions will make it harder to understand the language constructs. Skip this if you know how to write recursive functions.

The only way to define a function is by clauses of patterns and corresponding answers. So how can there be a non-trivial function? How can any problem requiring any repeated operation be solved? Even a problem as simple as computing the factorial of a number ``n'' would seem, in a procedural language, to require some repetition: ie. $1 * 2 * 3 \ldots * n$ .

The answer is to think of the solution to the problem in terms of clauses. All computably soluble problems have solutions that can be expressed in cases or patterns of actual arguments. Use the following approach:

Find simple immediate answers for the simple cases, and for all other cases express the answer as some operation on the result of an application of the same function on a simpler argument (ie. one tending towards the simple cases).

Using the function to define itself is recursion, if you are not confident about it still do it - it will work - do it as an act of faith, just believe!

To take that trivial problem of the factorial, observe that the factorial of 0 is defined to be 1, that's the simple case, and for all other values ^5.4 (other case) the factorial of any number ``n'' is ``n'' multiplied by the factorial of the previous number. In Haskell:

        factorial 0 = 1
        factorial n = n * factorial (n-1)

notice that the second case is an operation on the result of an application of the function being defined but with an argument tending towards the simple case, using factorial to define factorial is the act of faith.

The previous interlude about thinking of functional language evaluation in terms of rewriting names by their definitions can be used to assist understanding recursion:

factorial 3	matches the 2nd clause, n=3 and rewrites to:
3 * factorial (3-1)	just replacing factorial 2 rewrite to:
3 * 2 * factorial (2-1)	rewriting factorial 1 by 2nd clause:
3 * 2 * 1 * factorial (1-1)	factorial 0 matches 1st clause and rewrites to 1:
3 * 2 * 1 * 1	which by arithmetic gives:
6	done!

Recursion works over lists, following the magic recipe: first identify the simple answers then the cases for which the result is an operation on a recursive application with a simpler argument. But this time the simple case is likely to be [] not 0 and the simpler argument will be the tail of the list not a smaller number. For example to find the length of a list, observe that the empty list is 0 elements long and all other lists are one longer than lists one element shorter, so:

        len [] = 0
        len (h:t) = 1 + len t

Now rewrite len [4,5,6] which is equivalent to len (4:(5:(6:[])))

len [4,5,6]	matches len (h:t) binding h=4 and t=[5,6] giving:
1 + len [5,6]	replacing len [5,6] by rhs where h=5 and t=[6]
1 + 1 + len [6]	again with h=6 and t=[] gives:
1 + 1 + 1 + len []	len[] matches first clause and gives:
1 + 1 + 1 + 0	which by arithmetic gives:
3

One further example of a function on lists, this time to illustrate that values are not changed and if necessary new values (lists) must be constructed. The function takefirst n l will take the first n elements of the list l and make a list of them, so:

        takefirst 4 [10,9,8,7,6,5,4]

will give: [10,9,8,7]. Now the function:

        takefirst 0 any   = []
        takefirst n []    = error "list too short"
        takefirst n (h:t) = h : takefirst (n-1) t

This is the end of the interlude on recursion, now back to functions in Haskell.

Guarded expressions

For most functions simple clauses and patterns are not enough to select all the different cases for which different answers are required. For example a function to return the larger of two numbers cannot be done with patterns alone, selection of the result depends on a numeric comparison of the arguments and patterns are only constants, constructors or variables. Haskell provides alternative answers for each pattern's right hand side depending on the value of a boolean expression called a guard.

The last guard for one pattern can be the word ``otherwise''. For example to return the larger of two numbers:

        larger a b | a>=b = a 
                   | a<b  = b

note that a and b match any arguments, the two cases are selected by evaluating the guards in order until one gives true and then evaluating the following expression as the result. Relying on the order and using ``otherwise'':

        larger a b | a >= b = a 
                   | otherwise = b

though perhaps it is safer to use mutually exclusive guard conditions.

Multiple pattern clauses and guards can be combined. The following function isin tests to see whether a list contains a particular value:

        isin [] e = False             -- nothing in empty list
        isin (h:t) | h == e = True    -- is head the goal?
                   | h /= e = isin t e

Each clause is a separate equation and the bindings of the variables in the patterns only hold throughout the corresponding right hand side. The first rule has no bindings for h and t they are in a different equation but the second equation has two parts and h and t are bound through both expressions and both guards.

Where definitions and scope

The right hand side of a clause (just one clause and all its guarded expressions) can have local definitions. These definitions are within the scope of the pattern match for the clause so they can use the argument names and the values they define can be used throughout the guarded expressions. They can be used to avoid writing repeated expressions and to make the code clearer if it is long. The following function uses an auxiliary definition it its third equation:

        largest  []    = error "no largest in empty list"
        largest (h:[]) = h
        largest (h:t) | h>l  = h
                      | h<=l = l  
                          where l = largest t

If the where is not used the recursive call, largest t, to find the largest item in the tail of the list will be needed by the guard to compare it with the head item and again, maybe, as the result. The function would be as follows:

        largest  []    = error "no largest in empty list"
        largest (h:[]) = h
        largest (h:t) | if h>largest = h
                      | otherwise    = largest t

Note that the otherwise is to avoid using largest t three times!

Footnotes

... list ^5.3

The function front isn't really necessary as there is a pre-defined Haskell function called head which does the same.

... values ^5.4

Please assume non-negative arguments only for now

Page generated: 2002-11-04 by Bob Dickerson

© University of Hertfordshire Higher Education Corporation (1998)

Disclaimer