6.7 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:
(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.
|
| Name | Description |
|
| all l | and all the elements of list l together |
any l | or all the elements of list l together |
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 |
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 |
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 |
product l | product of list l |
repeat x | make an infinite list of xes |
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 |
splits fn l | break list l into single 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 |
sum l | sum list l |
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 |
|
| |
Table 6.3: | Functions in the standard list-processing toolkit |
|