Higher Order Functions in Practice
One of the best features that Javascript has to offer is that it treats functions as first class citizens. In fact one could argue (without causing a huge flame war) that Javascript is to date, one of the most widespread functional language. In this post I will explain what a higher order function is and illustrate how we can make use of higher order functions to simplify our code.
Summing things up!
Imagine you are given the task of writing a function which computes the sum of integers between a
and b
(inclusive). You open up your favourite editor (vim!) and quickly write the sumInts
function using recursion as follows:
function sumInts(a, b){
return (a > b) ? 0: a + sumInts(a+1, b);
}
Now you are given the task of writing a function which computes the sum of the cube of all integers between a
and b
. Using a similar approach you write the following:
function cube(a){
return a * a * a;
}
function sumCubes(a, b){
return (a > b) ? 0: cube(a) + sumCubes(a+1, b)
}
Now you are given the task of writing the sum of the factorials of all integers between a
and b
. So you write the following funciton:
function factorial(x){
return (x==0) ? 1 : x * factorial(x - 1);
}
function sumFactorials(a, b){
return (a > b) ? 0: factorial(a) + sumFactorials(a+1, b)
}
Now you are given … well you get the point. Looking closely at sumInts
, sumCubes
, and sumFactorials
you can observe that they have the same form.
function sum(a, b){
return (a > b) ? 0: <action>(a) + sum(a+1, b)
}
In mathematics we can express the three problems above as special cases of:
\[\sum_{x=a}^{b}f(x)\]In mathematics we do not write down three different \(\sum\) functions but instead we concentrate on the different values of \(f\). Using higher order functions we can express the \(\sum\) function as follows:
function sum(f, a, b) {
return (a > b) ? 0: f(a) + sum(f, a + 1, b);
}
The parameter f
is a placeholder for an action that we want to perform. You can think of f
as a mini program that will be executed when f(a)
is called.
Having created the higher order funciton sum
we can now write sumInts
, sumCubes
and sumFactorials
as follows:
function sum(f, a, b) {
return (a > b) ? 0: f(a) + sum(f, a + 1, b);
}
function sumInts(a, b) {
function id(x) {return x;}
return sum(id, a, b);
}
function sumCubes(a, b) {
return sum(cube, a, b);
}
function sumFactorials(a, b) {
return sum(factorial, a, b);
}
Anonymous Functions
Passing functions as parameters leads to the creation of many small functions. This is tedious and is not something we do with other value types. Let us for example consider how we would implement a simple “hello world” in Javascript. One could implement it as follows:
var s = "hello world!";
console.log(s);
but this is not natural, what we normally do is inline the string in the function call
console.log("hello world!");
Anaolgously, we can create function literals which let us inline functions without giving them a name. These are called anonymous functions. Using this technique we can write the sumInts
and sumCubes
as follows:
function sum(f, a, b) {
return (a > b) ? 0: f(a) + sum(f, a + 1, b);
}
function sumInts(a, b) {
return sum(function (x) {return x;}, a, b);
}
function sumCubes(a, b) {
return sum(function (x) {return x * x * x;}, a, b);
}
sumFactorial
makes use of the factorial
function which is recursive we cannot write it down using an anonymous functions (or at least not as succinctly). Be careful not to go overboard with anonymous functions; only use them when necessary.
Parameter Groups
Look closely at the function definitions we just defined.
function sumInts(a, b) {
return sum(function (x) {return x;}, a, b);
}
function sumCubes(a, b) {
return sum(function (x) {return x * x * x;}, a, b);
}
function sumFactorials(a, b) {
return sum(factorial, a, b);
}
Parameters a
and b
are passed unchanged from the sumInts
, sumCubes
and sumFactorials
into sum
. Can we get rid of this redundancy? Again we will make use of higher order functions to solve this problem as follows:
function sum(f) {
return function(a, b) {
return (a > b) ? 0: f(a) + sum(f)(a + 1, b);
};
}
The sum
funciton is now returning back a function which takes parameters a
and b
. Think of the sum
function as a function which takes two parameter groups; the first parameter group takes in the action f
and the second parameter group takes in the range [a
, b
]. Using this approach we can now simplify further the sumInts
, sumCubes
and sumFactorials
as follows:
var sumInts = sum(function(x){return x;});
var sumCubes = sum(function(x){return x * x * x; });
var sumFactorials = sum(factorial);
If we have a single call to sumInts
, sumCubes
and sumFactorials
for a specific range say [1,10], we can avoid creating the middlemen variables altogether by writing these functions as follows:
// sumInts
sum(function(x){return x;})(1, 10);
// sumCubes
sum(function(x){return x * x * x; })(1, 10);
// sumFactorials
sum(factorial)(1, 10);
To understand this notation let us take a look at the sum(function(x){return x*x*x;})(1,10)
. The other functions follow the same logic.
sum(function(x){return x*x*x;})
applies thecube
tosum
and returns the sum of cubes function.sum(function(x){return x*x*x;})
is therefore equivalent tosum(cube)
which is equivalent to our originalsumCubes
.- This function is applied to the arguments
(1, 10)
.