9.2 Higher-Order Functions
The function_points function is an example of a class of functions which we call higher-order. A higher-order function is a function that receives other functions as arguments or returns other functions as result. In the case of the function_points function, it receives as a parameter a function that will be called for successive points of an interval, producing the array of the found coordinates.
Higher-order functions are important tools for abstraction. They allow the abstraction of computations in which there is a part that is common and one (or more) parts that vary from case to case. Using a higher-order function, we only implement the part of the computation that is common, leaving the variable parts of the computation to be implemented as functions that will be passed in the parameters of the higher-order function.
The concept of higher-order function exists for a long time in mathematics, although rarely explicitly mentioned. Let us consider, for example, a function that sums the logarithms of all integers between \(a\) and \(b\), \(\sum_{i=a}^{b}\log{i}\):
sum_log(a, b) =
if a > b
0
else
log(a)+sum_log(a+1, b)
end
> sum_log(1, 4)
3.1780538303479458
Let us now consider another function that sums the square roots of all the integers between \(a\) and \(b\), \(\sum_{i=a}^{b}\sqrt{i}\):
sum_square_roots(a, b) =
if a > b
0
else
sqrt(a)+sum_square_roots(a+1, b)
end
> sum_square_roots(1, 4)
6.146264369941973
The observation of the functions’ definition shows that they have a common structure, characterized by the following definition:
sum_???(a, b) =
if a > b
0
else
???(a)+sum_???(a+1, b)
end
This definition is no more than a sum of a mathematical expression between two limits, i.e., a summation \(\sum_{i=a}^{b}f(i)\). The summation is an abstraction for a sum of numbers described by a mathematical expression relative to the summation index \(i\), which ranges from the lower limit \(a\) to the upper limit \(b\). The mathematical expression is, therefore, a function of the summation index.
The symbol ??? represents the mathematical expression to perform inside the sum, which we will simply transform into a parameter, by writing:
summation(f, a, b) =
if a > b
0
else
f(a)+summation(f, a+1, b)
end
We can now easily evaluate different summations:
> summation(log, 1, 4)
3.1780538303479458
> summation(sqrt, 1, 4)
6.146264369941973
Because it accepts a function as an argument, the summation is a higher-order function. The derivative of a function is another example. The derivative \(f'\) of a function \(f\) is a function that receives another function \(f\) as argument and returns a function - the derivative function of \(f\) - as a result.
Generally, higher-order functions arise because there are two or more functions with a similar structure. In fact, the repetition of a pattern along two or more functions is a strong indicator of the need for a higher-order function.