Going Functional: Higher-order functions

Introduction

Functional programming has been taking the world of software development by storm. The concept is not new, and it predates the advent of high-level programming languages as we know them, taking its roots in lambda calculus.

In this series, I'll aim to explain some functional programming concepts, and apply them to some problems, to show just how easy it can make the expression of concepts central to many domains where programming is used and as a bonus, how simple the code using it becomes, once one is familiar with its concepts.

The Problem

I will use this problem to exemplify the important concept of higher-order functions in the context of FP (functional programming, for short).

This problem was asked by Jane Street.

cons(a, b) constructs a pair, and car(pair) and cdr(pair) returns the first and last element of that pair. For example, car(cons(3, 4)) returns 3, and cdr(cons(3, 4)) returns 4.

Given this implementation of cons:

def cons(a, b):
     def pair(f):
        return f(a, b)
    return pair

Implement car and cdr.

So we need to implement two functions, car and cdr that return the first and second elements of a pair, respectively.

First, some concepts. (Sidenote: This explains the meaning behind the names for these functions. Blame late 50s :D )

Functions, closures... higher-order functions

Simple functions

A function in its most common form, can be seen as a small, cohesive unit that does some task, and can or not, produce a result to be used somewhere else.

def f(a,b):
  return a+b

Our function f above, takes two arguments and returns as a result the sum of the two.

This is a simple function, since it returns a value as a result.

Closures

A closure can be seen as a data structure holding together a function and it's surrounding environment (scope). Looking at the HaskellWiki, we get this definition:

A closure, the opposite of a combinator, is a function that makes use of free variables in its definition. It 'closes' around some portion of its environment.

In the Lambda Calculus, there are functions that have "free variables", meaning that they use variables that were not passed as direct parameters to them. Functions with free variables are what we call "closures" in this case.

In our example problem, the inner function, pair is a closure, since it uses the variables a and b that are defined on the outer scope (at the cons level).

Higher-order functions

A closure can be seen as a particular example of a higher-order function, it receives some parameters as input, and it's return result is a function in itself, which can be used and passed around as any other variable would.

Here's what happens in the Python interpreter:

>>> def cons(a, b):
...     def pair(f):
...             return f(a,b)
...     return pair
... 
>>> myfunc = cons(1,2)
>>> myfunc
<function pair at 0x7f05403e6758>

So, we can see that myfunc is a variable of type function.

This makes sense, since we see that the inner function pair is returned from calling cons.

However, we can also see two more things:

1. pair itself receives a function, f as its argument, and, since it's a closure, it makes use of the arguments that are on a different scope and "closes" them within its own scope, by calling f with those arguments.

2. To solve the problem at hand, we will need to pass functions to functions.

A simple example of using higher-order functions

So let's now assume we want a function maxOfTwo that receives a pair as its argument and returns the largest element of the two.

Since we know we will need to pass a function to a function, let's first define what we need: a function to carry the operation of returning the largest argument of the two passed to it:

>>> def maxOfTwo(a,b):
...     if a >= b:
...             return a
...     else:
...             return b
... 
>>> maxOfTwo(4,5)
5
>>> maxOfTwo(5,5)
5
>>> maxOfTwo(55,5)
55
>>> x = maxOfTwo(1,2)
>>> x
2

So we can now use our function, assign variables to its return value, and it all works.

Now, to pass this function as argument to cons, we can pass our function object as argument of our previously defined variable myfunc:

>>> myfunc = cons(1,2)
>>> myfunc(maxOfTwo)
2

Note how we are doing something interesting here:

we are using functions as values

In FP, a function can receive other functions and treat them as normal values that are passed around.

This is a very powerful idea because it allows to create very abstract and generic runtime constructs that allow for a lot of flexibility.

So to conclude, to solve our problem, car should receive a function that receives two arguments and returns the first one, and cdr, the second one:

Using closures, we can get this solution:

>>> def car(p):
...     def getFirst(x,y):
...             return x
...     return p(getFirst)
... 
>>> car(cons(3,4))
3
>>> 

>>> def cdr(p):
...     def getSecond(x,y):
...             return y
...     return p(getSecond)
... 
>>> cdr(cons(3,4))
4
>>> 

Conclusions

I hope you understood some new things and hope you understand a bit more about closures, higher-order functions and how to apply them.

In the next installment, I'll discuss lambda functions, and we will see how to implement powerful functional constructs with what we already know!