# GIML: Lesson Six

## Common recursive patterns

`map`

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`

`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 [i_{1}, i_{2}, i_{3}] = f(i_{1}, f(i_{2}, f(i_{3}, 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]];
`fold`

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`

`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`

`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]