General Computation Methods as Higher-Order Functions

So far, we’ve mainly defined functions whose arguments or return values are numbers, boolean values, or strings. But recall that functions are first-class citizens in functional programming languages. Thanks to this, we can easily define a function that accepts other functions as arguments or returns another function as a result. Such a function is called a higher-order function. High-order functions are powerful because they enable us to formulate computation patterns that work with different functions.

Summation as a higher-order function

A good way to appreciate the power of functions operating on other functions is to look at summation in mathematics. For instance, mathematicians often study summations, sums of a sequence of numbers, like the sum of all natural numbers from 1 to $n$:

$1 + 2 + 3 + \ldots + n$

Or the sum of squares of natural numbers from 1 to $n$:

$1^2 + 2^2 + 3^2 + \ldots + n^2$

If we look at these sums of sequences, we can notice that summation can be defined for any function capable of producing the terms for the sum. Of course, mathematicians realized this a long time ago. They invented the summation symbol $\sum$ (read “sigma”) to express the sum of elements represented by a function $f$ within an interval, $[m, n]$.

$\sum_{i = m}^{n}\,f(i) =f(m) + f(m + 1) + \ldots + f(n)$

The following diagram illustrates how the concept of summation is a generalization of more concrete sum concepts: