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

`f`

. In
the same way, the result list has type `f`

(in our `halve`

example, `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 typeand an*α*→ booland returns a list of just those elements of the argument list for which the given function returns*α*list`true`

.Write the function

`for_all`

which, given a function of typeand an argument list of type*α*→ boolevaluates to*α*list`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 typeover a list of type*α*→*β*to produce a list of type*α*list list.*β*list list