Higher-order functions

In the previous chapter two small functions were defined which performed very similar tasks. The sum' function added the numbers between 1 and n. The sq function added the terms 2i-1 for i between 1 and n. We will distill out the common parts of both functions and see that they can be used to simplify the definitions of a family of functions similar to sum' and sq. The common parts of these two functions are:

• a contiguous range with a lower element and upper element;
• a function which is applied to each element in turn;
• an operator to combine the results; and
• an identity element for the operator.

We will define a function which takes a five-tuple as its argument. Two of the elements in the five-tuple are themselves functions and it is for this reason that the function is termed higher-order. Functions which take functions as an argument--or, as here, as part of an argument--are called higher-order functions.

The function we will define will be called reduce. Here is the task we wish the reduce function to perform.

reduce (g, e, m, n, f) = g(f(m), g(f(m+1), ... g(f(n), e) ... ))

The function g may be extremely simple, perhaps addition or multiplication. The function f may also be extremely simple, perhaps the identity function, fn x => x.

In order to implement this function, we need to decide when the reduction has finished. This occurs when the value of the lower element exceeds the value of the upper element, m > n. If this condition is met, the result will be the identity element e. If this condition is not met, the function g is applied to f m and the value obtained by reducing the remainder of the range.

We would like the structure of the implementation to reflect the structure of the analysis of termination given above so we shall implement a sub-function which will assess whether or not the reduction has finished. The scope of this definition can be restricted to the expression in the body of the function.

val rec reduce = fn (g,e,m,n,f) =>
  let val finished = fn true  => e
                      | false => g (f m, reduce(g, e, m+1, n, f))
  in finished (m>n)
  end;

The Standard ML language has the property that if all occurrences in a program of value identifiers defined by nonrecursive definitions are replaced by their definitions then an equivalent program is obtained. We shall apply this expansion to the occurrence of the finished function used in the reduce function as a way of explaining the meaning of the let .. in .. end construct. The program which is produced after this expansion is performed is shown below.

val rec reduce = fn (g,e,m,n,f) =>
  (fn true  => e
    | false => g (f m, reduce(g, e, m+1, n, f))) (m>n);

The two versions of reduce implement the same function but obviously the first version is much to be preferred; it is much clearer. If the finished function had been used more than once in the body of the reduce function the result after expansion would have been even less clear. Now we may redefine the sum' and sq functions in terms of reduce.

val sum' = fn n => reduce (fn (x, y) => x+y, 0, 1, n, fn x => x);
val sq = fn n => reduce (fn (x, y) => x+y, 0, 1, n, fn x => 2*x-1);

Note that the function fn (x, y) => x+y which is passed to the reduce function does nothing more than use the predefined infix addition operation to form an addition function. Standard ML provides a facility to convert infix operators to the corresponding prefix function using the op keyword. Thus the expressions (op +) and fn (x, y) => x+y denote the same function. We will use the op keyword in the definition of another function which uses reduce, the factorial function, fac. The factorial of n is simply the product of the numbers from 1 to n.

val fac = fn n => reduce (op *, 1, 1, n, fn x => x);

Notice that if it is parenthesized, ``(op * )'' must be written with a space between the star and the bracket to avoid confusion with the end-of-comment delimiter.