A Quick View on Higher order functions

In mathematics and computer science, a higher-order function (also functional, functional form or functor; not to be confused with the functor concept in category theory) is a function that does at least one of the following:

takes one or more functions as arguments,
returns a function as its result.
In the untyped lambda calculus, Higher order functions assume that for T1,T2,T3 functions a map of (T1->T2)->T2 is equivalent to T1->(T2->T3).
But how are these applicable in programming? With examples inspired from Functional Programming book authored by Martin Odersky I will demonstrated the beauty of higher order functions within the context of Functional programming.
I will use Scala since if found it more mathematical native and originates in the depth of lambda calculations. Scala has always been my programming language of preference when it comes to express mathematical thinking.
I will start with two examples developed in an imperative style and then improve the algorithm with higher order functions injection.
Example 1: Let’s write a program that calculate the sum of squares between two points a and b.
The function square f mapped to x is defined as X->f(x)=x*x and the sum of square between a and be will be (a,b)∑f(x) with f(x)=x*x where x evaluates to all points between a and b.
Let’s define then our two functions square and sumSquares
def square(x: Double): Double = x * x
def sumSquares(a: Int, b: Int): Double =
if (a > b) 0 else square(a) + sumSquares(a + 1, b)
if we call this function as sumSquares(2,3) it would return 13 as expected.
Example 2: Let’s write a program that computes the sum of square-roots between two points a and b
A common way to compute square roots is by Newton’s method of successive ap-
proximations. One starts with an initial guess y (say: y = 1 ). One then repeatedly
improves the current guess y by taking the average of y and x/y . As an example, the next three columns indicate the guess y , the quotient x/y , and their average for the first approximations of square root of 2.
1 2/1=2 1.5
1.5 2/1.5=1.333 1.4167
1.4167 2/1.4167=1.4118 1.4142
… …. …..
y x/y (y+x/y)/2
Let’s implement this algorithm in Scala
def sqrt(x: Double) = {
def sqrtIter(guess: Double): Double =
if (isGoodEnough(guess, x)) guess
else sqrtIter(improve(guess))
def improve(guess: Double) =
(guess + x / guess) / 2
def isGoodEnough(guess: Double, x: Double) =
abs(square(guess) – x) / x < 0.00000001 sqrtIter(1) } This function checks every time if our guess is good enough by doing a square of the guess minus the value we wanted to determine its square root. If the result is approximately zero then the value is good enough. Note that this function may not converge for big values or smaller values since the gap between the square and the original value might be big. By dividing the subtraction of the square of the guess and the value x by x we narrow the gap. def sumOfSquareRoot(a: Double, b: Double): Double = if (a > b) 0 else sqrt(a) + sumOfSquareRoot(a + 1, b)
By calling this function sumOfSquareRoot(2,3) we would get approximately 3 which is exactly what we expected.
If you observe the two examples there are similarities. Both functions use (a,b)∑f(x).
How can we generalise the call to (a,b)∑f(x) in order to have one function that handle both sum of squares and sum of square roots? That is where higher order functions become handy.

I will straight show what the higher order function for the above examples would look like without going into details on how the compiler will interpret it but if you observe the example carefully you will notice without difficulty that I am just applying lambda calculations theory.

def sum(f: Double => Double): (Double, Double) => Double = {
def sumF(a: Double, b: Double): Double =
if (a > b) 0 else f(a) + sumF(a + 1, b)
sumF
}
And our sum functions will be modified like this:
def sumSquares = sum(square) // sumSquares: => (Double, Double) => Double
def sumOfSquareRoot = sum(sqrt) // sumOfSquareRoot: => (Double, Double) => Double
I have added comments to show that both functions sumSquares and SumofSquareRoot take one parameter which is the function that evaluate the expression of what we want to evaluate for a specific point and then return a function that in turn takes two parameters of the current point and the maximum point. The inner function is called and called again until the function falls within a range where a > b.
As you can see Higher functions are very handy and easy to understand. Once you pick the logic up you will never get rid of them in your daily programming. You can build on the above example codes to compute the sum of points between a and b, the sum of 2 squared n with n representing the set of points between a and b. etc,… for the sake of exercising just try to expand my examples and let me know what you think.

Leave a Reply

Your email address will not be published. Required fields are marked *