Often we need to apply a function to every element of a list. For example, doubling each of the numbers in a list of integers. We could do this with a simple recursive function, working over each element of a list:
For example,
The result list does not need to have the same type as the argument
list. We can write a function which, given a list of integers, returns
the list containing a boolean for each: true if the number
is even, false if it is odd.
For example,
It would be tedious to write a similar function each time we wanted to apply a different operation to every element of a list – can we build one which works for any operation? We will use a function as an argument:
The map function takes two arguments: a function which
processes a single element, and a list. It returns a new list. We will
discuss the type in a moment. For example, if we have a function
halve:
We can use map like this:
Now, let us look at that type: (α → β) → α list → β list. We can annotate the individual parts:
We have to put the function f in parentheses, otherwise
it would look like map had four arguments. It can have any
type α →
β. That is to
say, it can have any argument and result types, and they do not have to
be the same as each other – though they may be. The argument has type
α list because each
of its elements must be an appropriate argument for f. In
the same way, the result list has type β
list because each of its elements is a result from
f (in our halve example, α and β were both int). We can rewrite our
evens function to use map:
In this use of map, α was int, β was bool. We can make evens
still shorter: when we are just using a function once, we can define it
directly, without naming it:
This is called an anonymous function. It is defined using
fun, a named argument, the -> arrow and the
function definition (body) itself. For example, we can write our halving
function like this:
fun x -> x / 2
and, thus, write:
We use anonymous functions when a function is only used in one place and is relatively short, to avoid defining it separately.
In the preceding chapter we wrote a sorting function and, in one of
the questions, you were asked to change the function to use a different
comparison operator so that the function would sort elements into
reverse order. Now, we know how to write a version of the
msort function which uses any comparison function we give
it. A comparison function would have type α → α
→ bool. That is, it
takes two elements of the same type, and returns true if
the first is “greater” than the second, for some definition of “greater”
– or false otherwise.
So, let us alter our merge and msort
functions to take an extra argument – the comparison function:
Now, if we make our own comparison operator:
we can use it with our new version of the msort
function:
In fact, we can ask OCaml to make such a function from an operator
such as <= or + just by enclosing it in
parentheses and spaces:
OCaml
# ( <= )
- : 'a -> 'a -> bool = <fun>
# ( <= ) 4 5
- : bool = true
So, for example:
and
The techniques we have seen in this chapter are forms of program reuse, which is fundamental to writing manageable large programs.
Write a simple recursive function calm to replace
exclamation marks in a char
list with periods. For example
calm [’H’; ’e’; ’l’; ’p’; ’!’; ’ ’; ’F’; ’i’; ’r’; ’e’; ’!’]
should evaluate to
[’H’; ’e’; ’l’; ’p’; ’.’; ’ ’; ’F’; ’i’; ’r’; ’e’; ’.’].
Now rewrite your function to use map instead of recursion.
What are the types of your functions?
Write a function clip which, given an integer, clips
it to the range 1…10 so that integers
bigger than 10 round down to 10, and those smaller than 1 round up to 1.
Write another function cliplist which uses this first
function together with map to apply this clipping to a
whole list of integers.
Express your function cliplist again, this time
using an anonymous function instead of clip.
Write a function apply which, given another
function, a number of times to apply it, and an initial argument for the
function, will return the cumulative effect of repeatedly applying the
function. For instance, apply f 6 4 should return
f (f (f (f (f (f 4)))))). What is the type of your
function?
Modify the insertion sort function from the preceding chapter to take a comparison function, in the same way that we modified merge sort in this chapter. What is its type?
Write a function filter which takes a function of
type α →
bool and an α list and returns a
list of just those elements of the argument list for which the given
function returns true.
Write the function for_all which, given a function
of type α →
bool and an argument list of type α
list evaluates to true if and only if the
function returns true for every element of the list. Give
examples of its use.
Write a function mapl which maps a function of type
α →
β over a list
of type α list list to
produce a list of type β list
list.