Next: 6.9 Lazy programming Up: 6. Programming Previous: 6.7.7 The image type Contents

#
6.8 Lists and recursion

Functional programming languages do not have variables, assignment or iteration. You can achieve the same effects using just lists and recursion.

There are two main sorts of recursion over lists. The first is called mapping: a function is applied to each element of a list, producing a new list in which each element has been transformed.

> | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> | `map fn [a,b,c] == [fn a, fn b, fn c]` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

The second main sort of recursion is called folding: a list is turned into a single value by joining pairs of elements together with a function and a start value.

> | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> | `foldr fn start [a,b .. c] ==` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> |  |  |  | `(fn a (fn b (.. (fn c start))))` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

(The function is called `foldr` as it folds the list up right-to-left. There is an analogous function called `foldl` which folds a list up left-to-right, but because of the way lists work, it is much slower and should be avoided if possible.)

`map` is defined in the standard list library for you:

> | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> | `/* map fn l: map function fn over list l` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> | `*/` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> | `map fn l` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> |  | `=` |  | `[], l == []` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> |  | `=` |  | `fn (hd l) : map fn (tl l)` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

So, for example, you could use `map` like this:

> | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> | `map (add 2) [1..5] == [3,4,5,6,7,8]` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

`foldr` is defined in the standard list library for you:

> | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> | `/* foldr fn st l: fold up list l, right to` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> | `* left with function fn and start value st` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> | `*/` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> | `foldr fn st l` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> |  | `=` |  | `st, l == []` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> |  | `=` |  | `fn (hd l) (foldr fn st (tl l))` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

So, for example, you could use `foldr` like this:

> | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` | `` |  | `` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
> | `foldr add 0 [1..5] == 15` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

(Mathematically, `foldr` is the more basic operation. You can write `map` in terms of `foldr`, but you can't write `foldr` in terms of `map`.)

Unconstrained recursion over lists can be very hard to understand, rather like `goto` in an imperative language. It's much better to use a combination of `map` and `foldr` if you possibly can.

The toolkit `_list` contains definitions of most of the standard list-processing functions. These are listed in Table 6.3. Check the source for detailed comments.

Table 6.3: Functions in the standard list-processing toolkit
Name | Description
`concat l` | join a list of lists together
`drop n l` | drop the first `n` elements from list `l`
`dropwhile fn l` | drop while `fn` is true
`extract n l` | extract element `n` from list `l`
`filter fn l` | all elements of `l` for which `fn` holds
`foldl fn st l` | fold list `l` left-to-right with `fn` and `st`
`foldl1 fn l` | like `foldl`, but use the first element of the list as the start value
`foldr fn st l` | fold list `l` right-to-left with `fn` and `st`
`foldr1 fn l` | like `foldr`, but use the first element of the list as the start value
`index fn l` | search list `l` for index of first element matching predicate `fn`
`init l` | remove last element of list `l`
`iterate f x` | repeatedly apply `f` to `x`
`land l` | and all the elements of list `l` together
`last l` | return the last element of list `l`
`len l` | find length of list `l`
`limit l` | find the first element of list `l` equal to its predecessor
`lor l` | or all the elements of list `l` together
`map fn l` | map function `fn` over list `l`
`map2 fn l1 l2` | map 2-ary function `fn` over lists `l1` and `l2`
`map3 fn l1 l2 l3` | map 3-ary function `fn` over lists `l1`, `l2` and `l3`
`member l x` | true if `x` is a member of list `l`
`mkset l` | remove duplicates from list `l`
`postfix l r` | add element `r` to the end of list `l`
`repeat x` | make an infinite list of `x`es
`replicate n x` | make `n` copies of `x` in a list
`reverse l` | reverse list `l`
`scan fn st l` | apply `(foldr fn r)` to every initial segment of list `l`
`sort l` | sort list `l` into ascending order
`sortc fn l` | sort list `l` into order by using a comparison function
`sortpl pl l` | sort list `l` by predicate list `pl`
`sortr l` | sort list `l` into descending order
`split fn l` | break list `l` into sections separated by predicate `fn`
`splitpl pl l` | break list `l` up by predicate list `pl`
`split_lines n l` | break list `l` into lines of length `n`
`take n l` | take the first `n` elements from list `l`
`takewhile fn l` | take from the front of `l` while `fn` holds
`zip2 l1 l2` | zip two lists together
`zip3 l1 l2 l3` | zip three lists together

Next: 6.9 Lazy programming Up: 6. Programming Previous: 6.7.7 The image type Contents