Back to Contents

# Functions upon Functions upon Functions

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.

## Questions

1. 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?

2. 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.

3. Express your function cliplist again, this time using an anonymous function instead of clip.

4. 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?

5. 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?

6. 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.

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

8. 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.