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);


reduce takes a binary function (a function with two inputs) a base value and a list. It applys the function repeatedly down the list. For example
reduce f b [i1, i2, i3] = f(i1, f(i2, f(i3, b)))
Consider 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]];


The predefined function fold is the same as reduce - but the arguements are in a different order. We might have defined reduce as..
fun reduce f b l = fold f l b; 


zip can be used to apply a binary function (one with two inputs) to the corresponding elements of two lists. For example
zip (op +) [1,2,3] [2,4,6] = [3,6,9]
zip is defined as follows
fun zip f nil nil = nil
|   zip f (h::t) (i::u) = f(h,i)::zip f t u;


filter takes a predicate (a function which returns true or false) and a list. It returns the list with only those items for which the predicate s true.

Suppose the function even : int -> bool has been defined as

fun even n = (n mod 2 = 0);
then applying filter even over the list [1,2,3,4,5,6] would return only the even values.
filter even [1,2,3,4,5,6] = [2,4,6]