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:
<![CDATA[fun doublist nil = nil
| doublist(h::t) = 2*h :: (doublist t);
fun inclist nil = nil
| inclist(h::t) = (h+1) :: (inclist t);
]]>
Typical executions:
<![CDATA[
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:
<![CDATA[fun map f nil = nil
| map f (h::t) = (f h)::(map f t);
]]>Alternative definitions for doublist and inclist are
<![CDATA[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)
<![CDATA[fun sum nil = 0
| sum(h::t) = h + sum t;
fun flatten nil = nil
| flatten (h::t) = h @ flatten t;
]]>
Typical executions:
<![CDATA[
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:
<![CDATA[fun reduce f b nil = b
| reduce f b (h::t) = f(h,reduce f b t);
]]>We can now redefine sum and flatten:
<![CDATA[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.
<![CDATA[reduce (op +) 0 [1,2,3,4];
reduce (op @) nil [[1,2],[3,4],[5,6,7]];
]]>