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.

Incompleteness

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.

Further examples

Define the following functions and test them. You may wish to use the given input to get an idea of what they do. Some of the functions are partial, some have overlapping left hand sides. Determine if they are not defined or are "over defined". fun hdify nil = nil | hdify((h::_)::t) = h::(hdify t); fun tlify nil = nil | tlify((_::t)::t') = t::(tlify t'); fun trans (nil::_) = nil | trans x = hdify x ::(trans(tlify x)); fun altern(nil, nil) = nil | altern(h::t, h'::t') = h::h'::altern(t,t'); fun diff(nil,x) = x | diff(x,nil) = x | diff(_::t,_::t') = diff(t,t'); hdify [[1,2,3],[4,5,6],[7,8,9]]; tlify [[1,2,3],[4,5,6],[7,8,9]]; trans [[1,2,3],[4,5,6],[7,8,9]]; altern([1,2,3],[4,5,6]) diff([1,2,3,4],[5,6]) diff([1,2],[3,4,5,6])

Conditions

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" else x^"ed";

Anonymous function

A function may be defined with being named. The syntax is as follows fn <parameters> => <expression> For example - 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];