GIML: Lesson Five
Pattern matching and recursion
When defining a function over a list we commonly use the two patterns
fun lfun nil = ...
| lfun(h::t) = ... lfun t ...;
However this need not always be the case. Consider the function last, which returns the last element of a list.
last [4,2,5,1] = 1
last ["sydney","beijeng","manchester"] = "manchester"
The two patterns do not apply in this case. Consider the value of last nil. What is the last element of the empty list? This is not a simple question like "what is the product of an empty list". The expression last nil has no sensible value and so we may leave it undefined. Instead of having the list of length zero as base case we start at the list of length one. This is the pattern [h], it matches any list containing exactly one item.
fun last [h] = h
| last(h::t) = last t;
This function has two novel features.
When we enter the function as above ML responds with a warning such as
std_in:217.1-218.23 Warning: match non exhaustive
h :: nil => ...
h :: t => ...
The function still works, however ML is warning us that the function has not been defined for all values, we have missed a pattern - namely nil. The expression last nil is well-formed (that is it obeys the type rules) however we have no definition for it. It is an incomplete or partial function as opposed to the complete or total functions that we have seen thus far. You will naturally want to know how ML does treat the expression last nil.
The warning given is a mixed blessing. Under certain circumstances a partial function is very useful and there is no merit in making the function total. However if we manage to compile a program with no warnings and avoid all partial functions we are (almost) guaranteed no run-time errors. The exhaustive checking of input patterns can be non-trivial, in fact the algorithm which is used in non polynomial.
Overlapping left hand sides
As the pattern [h] is identical to the pattern h::nil we might rewrite the definition
fun last(h::nil) = h
| last(h::t) = last t;
Examining the patterns of the left hand side of the = we note that there is an overlap. An expression such as 5::nil will match with both the first equation (binding h to 5) and the second equation (binding h to 5 and t to nil). Clearly it is the first line which we want and indeed ML will always attempt to match with patterns in the order that they appear. Note that this is not really a novel feature as all of our first examples with the patterns x and 0 had overlapping left hand sides.
Where possible we use pattern matching to deal with conditions, in some cases this is not possible.
We return to the function to convert present to past tense. The general rule - that we append "ed" does not apply if the last letter of the verb is "e". We can examine the last character of the input by applying explode then rev then hd.
The improved version of past should give
past "turn" = "turned"
past "insert" = inserted"
past "change" = "changed"
The special case irregular verbs are dealt with as before:
fun past "run" = "ran"
| past "swim" = "swam"
| past x = if hd(rev(explode x))="e" then x^"d"
A function may be defined with being named.
The syntax is as follows
- fn x => 2*x;
> it = fn : int -> int
- it 14;
> 28 : int
This can be particularly useful when using higher order functions like map
map (fn x=> 2*x) [2,3,4];