GIML: Lesson Four

List processing and pattern matching

sum of a list

Consider the function sum which adds all the elements of a list. sum [2,3,1] = 2 + 3 + 1 = 6 There are two basic patterns for a list - that is there are two list constructors, :: and nil. The symbol :: is called cons, it has two components, nil is the empty list We can write equations for each of these constructors with completely general components. The empty list is easy - sum of all the elements in the empty list is zero. sum nil = 0 In the cons case we need to consider the value of sum(h::t). Where h is the head of the list - in this case an integer - and t is the tail of the list - i.e. the rest of the list. In constructing recursive functions we can assume that the function works for a case which is in some sense "simpler" than the original. This leap of faith becomes easier with practice. In this case we can assume that function sum works for t. We can use the value sum t on the right hand side of the definition. sum(h::t) = ??? sum(t); We are looking for an expression which is equal to sum(h::t) and we may use sum t in that expression. Clearly the difference between sum(h::t) and sum(t) is h. That is, to get from sum(t) to sum(h::t) simply add h fun sum nil = 0 | sum(h::t) = h + sum t;

appending (joining) two lists

The infix append function @ is already defined however we may derive its definition as follows The append operator joins two lists, for example [1,2,3] @ [4,5,6] = [1,2,3,4,5,6] The definition of an infix operator allows the left hand side to be written in infix. Given two parameters we have a choice when it comes to deciding how to recurse. If we choose to recurse on the second parameter the equations will be fun x @ nil = ?? | x @ (h::t) = ??; It turns out that this does not lead to a useful definition - we need to recurse on the first parameter, giving fun nil @ x = ?? | (h::t) @ x = ??; The first equation is easy, if we append nil to the front of x we just get x. The second equation is more difficult. The list h::t is to be put to the front of x. The result of this is h cons'ed onto the list made up of t and x. The resulting list will have h at the head followed by t joined onto x. We make use of the @ operator within its own definition. fun nil @ x = x | (h::t) @ x = h::(t @ x); Of course the @ operator is already defined. Note that the actual definition used is slightly different. Example: doublist Consider the function doublist which takes a list and doubles every element of it. doublist [5,3,1] = [10,6,2] Again we consider the two patterns nil and (h::t). The base case is nil doublist nil = nil A common mistake is to think doublist nil is 0. Just by looking at the type we can see that this would be nonsense. The output from doublist must be a list, not an integer. In considering the cons case an example may help. Imagine the execution of a particular list say doublist [5,3,1]. We rewrite [5,3,1] as 5::[3,1] and consider the second equation. doublist(5::[3,1]) = ??? doublist [3,1] Thanks to our faith in recursion we know that doublist[3,1] is in fact [6,2] and so we ask what do we do to [6,2] to get our required answer [10,6,2]. We answer "stick ten on the front". doublist(5::[3,1]) = 10::doublist [3,1] Returning to the general case with h and t instead of 5 and [3,1]: doublist(h::t) = 2*h :: doublist t

if .. then .. else ..

Sometimes pattern matching is not convenient. We may wish to compare values for example, in these cases the if .. then .. else .. structure is useful.

The expression if B then S1 else S2 tests the boolean expression B, it returns the value of S1 or the value of S2 depending on the value of B.

For example

if 1 = 0 then "I am the pope." else "someone else is the pope.";

Returns the string "someone else is the pope."

The following function "tells us" about a string s. A palimdrome is a word which is the same backwards as forwards.

fun pali s = if explode s = rev(explode s) then s ^ " is a palindrome."
					else s ^ " is not a palindrome.";

We can go further - the sentence is the same in both cases, except the substring "not " is missing in one case - this allows..

fun pal2 s = s^" is "^(if explode s = rev(explode s) then "" else "not ") ^
			"a palindrome.";

In some languages the else part is optional - that would make no sense in ML as the expression must return a value.

The @ operator

The append operator is defined in the file "/usr/local/software/nj-sml-93/src/boot/perv.sml" and is given as:

  infixr 5 :: @
  fun op @(x,nil) = x
    | op @(x,l) =
    let fun f(nil,l) = l
          | f([a],l) = a::l
        | f([a,b],l) = a::b::l
        | f([a,b,c],l) = a::b::c::l
        | f(a::b::c::d::r,l) = a::b::c::d::f(r,l)
     in f(x,l)

    end

This version may be shown to be equivalent to the simpler:

  infixr 5 :: @
  fun nil   @ l = l
  |   (h::t)@ l = h::(t@l)

but it will run faster.