GIML: Lesson Six
Common recursive patterns
You will have noticed that certain patterns crop up in recursive
functions. The following functions double and increment every item
in a list respectively:
fun doublist nil = nil
| doublist(h::t) = 2*h :: (doublist t);
fun inclist nil = nil
| inclist(h::t) = (h+1) :: (inclist t);
Typical executions:
doublist [1,2,3,4] = [2,4,6,8]
inclist [1,2,3,4] = [2,3,4,5]
Plainly we can abstract out of this a function which applies a function over a list. This is map:
fun map f nil = nil
| map f (h::t) = (f h)::(map f t);
Alternative definitions for doublist and inclist are
val doublist = map (fn x=>2*x);
val inclist = map (fn x=> x+1);
Slightly more subtle is the connection between the functions sum and flatten
(the function flatten turns a list of lists into a simple list)
fun sum nil = 0
| sum(h::t) = h + sum t;
fun flatten nil = nil
| flatten (h::t) = h @ flatten t;
Typical executions:
sum [10, 20, 30] = 60
flatten [[1,2],[3,4],[5,6,7]] = [1,2,3,4,5,6,7]
This second pattern is the reduce pattern - we have a base value for the nil list, for a cons node we apply a binary (two input) function f which is applied to the head and the recursive call:
fun reduce f b nil = b
| reduce f b (h::t) = f(h,reduce f b t);
We can now redefine sum and flatten:
val sum = reduce (fn(a,b)=>a+b) 0;
val flatten = reduce (fn(a,b)=>a@b) nil;
In fact we can do even better, ML allows use to convert infix functions such as + and @ into the prefix form required using the keyword op.
reduce (op +) 0 [1,2,3,4];
reduce (op @) nil [[1,2],[3,4],[5,6,7]];