Understanding High Order Functions (Pt. 1)
Higher Order Functions
Higher order functions, in functional programming languages, are functions that have one or both of the following properties:
- One or more parameters of the function take a function as an argument.
- The function evaluates to another function.
This tutorial will focus on the first property mentioned: functions that take other functions as arguments. Most of us are used to just passing values — integers, characters, and strings — to functions. The idea of passing a function to another function may seem foreign to most of us. Let's look at why this may be useful through an example in the introduction below:
Introduction
Suppose you want to take a list, or an array, of integers and get a list that contains all the integers doubled. For example, when given the list [1, 2, 3, 4, 5], the list [2, 4, 6, 8, 10] is returned. This can be done in imperative languages and object-oriented languages such as C++ as seen below.
int * doubleList(int integers[], int size){
int *doubleIntegers = (int*)malloc(sizeof(int) * size);
for(int i = 0; i < size; i++){
doubleIntegers[i] = integers[i] * 2;
}
return doubleIntegers;
}
We will call this list doubleList.
Now, suppose I want to create a list that contains all the integers tripled. I would have to create another method that would multiply every element in the list by 3 — let's call this method tripleList. Let's look at method doubleList and tripleList (given below).
int * tripleList(int integers[], int size){
int *tripleIntegers = (int*)malloc(sizeof(int) * size);
for(int i = 0; i < size; i++){
tripleIntegers[i] = integers[i] * 3;
}
return tirpleIntegers;
}
The only real difference between these two methods, besides the change in variable names, is the body of the for-loop; the only difference between the body is the number we are multiplying integers[ i ] by. I know you may be thinking, why not just pass the number you want to multiply the integers with as an argument to method? Maybe something like below:
int * xList(int integers[], int size, int x){
int *xIntegers = (int*)malloc(sizeof(int) * size);
for(int i = 0; i < size; i++){
xIntegers[i] = integers[i] * x;
}
return xIntegers;
}
Now we can do what we wanted to do, and some more!
int arr[5] = {1,2,3,4,5}
xList(arr, 5, 2) //doubles the list - returns [2,4,6,8,10]
xList(arr, 5, 3) //triples the list - returns [3,6,9,12,15]
xList(arr, 5, 4) //quadruples the list - returns [5,10,15,20,25]
xList(arr, 5, 5) //quintuples the list = retursn [5, 10, 15, 20, 25]
But wait, we still have some limitations. Suppose I want to square all the elements in the list — I would have to create a new method and there would be a lot of code duplication!
int * sqrList(int integers[], int size){
int *sqrIntegers = (int*)malloc(sizeof(int) * size);
for(int i = 0; i < size; i++){
sqrIntegers[i] = integers[i] * integers[i];
}
return sqrIntegers;
}
It would be nice if I could create a method that would take a list and the function that I want to perform on the elements in that list and return a list with the function applied to all the elements. Something like this:
//Not valid C++ code, example of what we would like to see
//The function, func, would be the operation we want applied to all elements of the list
int * funcList(int integers[], int size, function func){
int *evaluatedList = (int*)malloc(sizeof(int) * size);
for(int i = 0; i < size; i++){
evaluatedList[i] = func(integers[i]);
}
return evaluatedList;
}
//Example results we would like
int arr[5] = {1,2,3,4,5};
int doubleInt(int i) {return i * 2;} //An operation to double an integer
int tripleInt(int i){return i * 3;} //An operation to triple an integer
int quadrupleInt(int i){return i * 4;} //An operation to quadruple an integer
int sqrInt(int i){return i * i;} //An operation to square an integer
funcList(arr, 5, doubleInt); // would return [2, 4, 6, 8, 10]
funcList(arr, 5, tripleInt); // would return [3, 6, 9, 12, 15]
funcList(arr, 5, quadrupleInt); //would return [4, 8, 12, 16, 20]
funcList(arr, 5 sqrInt); //would return[1, 4, 9, 16, 25]
What we see is a method that takes a function and applies that function to every element of the list. Instead of writing multiple methods that do similar things (and creating a lot of code duplication), I wrote one method that takes an operation, the function, and apply that function to all the elements of the list. Sadly, there is no easy way of doing this in C++, but function programming languages, such as Haskell, supply a very easy way to do this. The function that takes a function and a list as its arguments and applies them to every element in the list is called the map function. The map function is built into a lot of functional programming languages, including Haskell! Let's take a look at the map function in Haskell.
Using the Map Function In Haskell
As previous stated, the map function is the name of the function that allows us to apply another function to every element of a list. Let's take a look at the map function in Haskell.
First, let's define some functions in Haskell that doubles, triples, quadruples, and squares a number.
--The functions
double x = x * 2
triple x = x * 3
quadruple x = x * 4
squares x = x * x
--Examples
double 2 --returns 4
triple 2 --returns 6
quadruple 2 --returns 8
squares 2 --returns 4
The map function in Haskell has the following format:
map func list
-- where func is the function to be applied to every element in the list
Below is an example of using the map.
theList = [1, 2, 3, 4, 5]
map double theList -- returns [2, 4, 6, 8, 10]
map triple theList -- returns [3, 6, 9, 12, 15]
map quadruple theList -- returns [4, 8, 12, 16, 20]
map squares theList --returns [1, 4, 9, 16, 25]
Notice that all we had to do is create a function that takes a single element. By using map we were able to apply that function to every element in the list. We were able to pass in the function we wanted to use as an argument to the map function! By doing so, we were able to reduce the amount of code duplication, which means we didn't have to write a separate map for each function we wanted applied. All we had to do was write the function and performed the operation we wanted and pass it to map.
Recap
A higher order function is a function that has at least one argument that is a function or returns as a function after it is evaluated (we will discuss these types of functions in part 2). The map function is a higher order function because it takes a function as an argument.
