The last part of this series introduced a basic technique in functional programming, namely recursion. Today we shall learn another important functional technique known as higher-order programming.

Patterns in Functions

Consider the following two functions. The first one computes the sum of integers from a through b:

fun sumInts (a, b) =
    if a > b then 0
    else a + sumInts (a + 1, b)

The second one computes the sum of the squares of the integers in the given range:

fun sumSquares (a, b) =
    if a > b then 0
    else (a * a) + sumSquares (a + 1, b)

You may have noticed that the two functions for the most part are identical. The only difference is the transformation applied to a before it is added to the running sum. Basically, these functions capture the general idea of “summation of a sequence”.

A powerful language should allow us to abstract the idea of summation itself so that all particular sums can be expressed in terms of a “universal” sum function.

Such abstractions can be easily built if the language treats functions as first-class types. A value of a first-class type can be:

  1. created on demand,
  2. passed to functions as arguments,
  3. returned by functions as results and
  4. stored in data structures.

We have already encountered many types that are first-class in SML - int, real, bool, string, char and tuple.

Functional languages assign first-class status to functions as well. This feature is at the core of building higher-order abstractions.

Higher-order Programming

Higher-order programming refers to a collection of programming idioms that becomes possible when a language has functions as first-class values.

Before we look at the details, here is the story behind the name:

A language that does not allow functions as arguments is known as a first-order language. A language that allows at least one first-order function as argument is of second-order and so on. A language that place no restrictions on functional arguments is a higher-order language. SML is a higher-order language.

We can express the “summation of a series” as a generic function by passing the “transformation” function as an extra argument:

fun sum (a, b, transform) =
    if a > b then 0
    else (transform a) + sum (a + 1, b, transform)

Assume that we have the square function defined below:

fun square x = x * x

Now we can define sumSquares in terms of sum by passing square as the transformer:

fun sumSquares (a, b) = sum (a, b, square)

What will be the transformer for sumInts? As the integers are not supposed to be transformed in any way, it has to be the identity function shown below:

fun identity x = x

The identity function simply returns its argument as result, performing no transformation at all. This leads to the following compact definition of sumInts:

fun sumInts (a, b) = sum (a, b, identity)

An aside on polymorphism

If you typed identity into the REPL, you might have noticed that its inferred type is val identity = fn : 'a -> 'a.

The identifiers beginning with the apostrophe (‘) are type variables. They denote types and not ordinary values. In the case of identity, SML has decided that the argument can be of any type and hence designates its type as 'a -> 'a. SML often uses type variables like 'a and 'b to represent the type of something that can be of any type.

A function that is able to admit arguments of many types are known as polymorphic (poly = many; morph = form). There is more to say about polymorphism, but let’s save that for a later post.

Function literals

While using higher-order functions, it seems inconvenient to have to define simple function like square. This is especially so if its only purpose is to serve as an argument to another function.

SML allows us to define functions as literal values, by using the keyword fn. Function values are also known as function expressions or anonymous functions.

Anonymous functions are declared with the syntax:

fn P => E

where P is the function’s parameter and E is its body.

Here is how we would define and use a throw-away square function:

- (fn x => x * x) 10;
(* val it = 100 : int *)

Anonymous functions are more useful when they are created on-demand to be used as arguments for other functions:

- fun sumSquares (a, b) = sum (a, b, fn (x) => x * x);
(* val sumSquares = fn : int * int -> int *)

- sumSquares (10, 20);
(* val it = 2585 : int *)

Generalizing Sum

We saw how to abstract the idea of “adding together the numbers in a sequence”. More generally the sum function we defined can be seen as a folder or a reducer because what it does is to reduce a sequence of numbers into a single value.

This reduction is achieved by interspersing the + operator within the sequence. The base case of the function returns 0, which is the identity element for addition. This is because, for any integer n, n + 0 = n.

With these concepts in mind, we can generalize sum even further to arrive at a function that can reduce a sequence using a binary operation like + and its matching identity element.

Here is the definition of the reduce abstraction:

fun reduce (a, b, id, opr, transform) =
    if a > b then id
    else opr ((transform a), reduce (a + 1, b, id, opr, transform))

To define sum in terms of reduce we should pass 0 as the value of the identity-element (id) parameter and + as the value of the operation (opr).

fun sum (a, b, transform) =
  reduce (a, b, 0, op +, transform)

Note: We can use an infix operator like + as a function by preceding it with the keyword op.

We shall also define a similar function for multiplying a sequence. For this, * is the binary operator and 1 is the identity element.

fun prod (a, b, transform) =
  reduce (a, b, 1, op *, transform)
-  prod (1, 10, fn x => x);
(* val it = 3628800 : int *)

Note: The mathematically inclined reader may recognize the reduce function as an expression of the Commutative monoid.

Conclusion

This post introduced higher-order programming. We saw the precise definition of this term and learned how to write simple higher-order functions.

In the next post we shall look at two other important functional programming techniques - function composition and partial evaluation.


Note that name and e-mail are required for posting comments