7.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 $\Sigma$ notation. This notation satisfies the following equations.

	$\displaystyle\sum_{k=1}^{0}f(k)$	$\displaystyle=$	$\displaystyle 0$
	$\displaystyle\sum_{k=1}^{n+1}f(k)$	$\displaystyle=$	$\displaystyle f(n)+\sum_{k=1}^{n}f(k)$

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 $\sum_{k=1}^{n}f(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,\ldots,n$ , and is not a real variable. The variables of this expression are $n$ and $f$ .
•

Expression $\sum_{k=1}^{n}f(k)$ denotes the value $f(1)+f(2)+\cdots+f(n)$ for any given integer $n$ and a function $f$ .

$\sum$ 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 (powerCurry 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 7.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.