Ch.6 Introduction to ML programming

§ 6.11. Using higher-order functions

The key to writing a cool, i.e. readable and concise program efficiently is to understand the role of higher-order functions and to compose expressions using higher-order functions. As in any programming skill, mastering higher-order functions require certain amount of practice, and is beyond this tutorial. However, there are few basic concepts that are important in writing expressions using higher-order functions. This tutorial attempt to exhibit them. In what follows, we learn these concepts through simple examples.

In high school mathematics, we have learned Σ notation. This notation satisfies the following equations.


The reason for learning this notation is because this notation represents a useful abstraction, i.e. summing up a sequence of expressions with integer indexes. A brief analysis of the notation k=1nf(k) reveals the following.

  • The notation contains 3 variables k,n,f. Among them, k is a variable that is only to indicate that expressions are index by k=1,,n, and is not a real variable. The variables of this expression are n and f.

  • Expression k=1nf(k) denotes the value f(1)+f(2)++f(n) for any given integer n and a function f.

is a function that takes an integer n and a function f that takes an integer and returns an integer, i.e. it is a higher-order function. In ML, this higher-order function is directly code as follows.

# fun Sigma f 0 = 0
         | Sigma f n = f n + Sigma f (n - 1)
val Sigma = fn : (int -> int) -> int -> int

This Sigma can compute the summation of any inter function.

# Sigma square 3:
val it = 14 : int
# Sigma (power 3) 3:
val it = 36 : int

As demonstrated by this example, higher-order functions has the power of representing a useful computation pattern by abstracting its components as argument functions. The key to writing a cool ML code is to master the skill of abstracting useful computation patterns as higher-order functions. Polymorphic typing we shall learn in Section 6.20 can be regarded as a mechanism to support this style of programming. Higher-functions with their polymorphic typing enable the ML programmer to code a complicated system in a concise and declarative way.