Going Functional: Higher-order functions 
Tags: goingfunctional, python, paradigm
Published: 2019-08-18 16:57:50

**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:
> ```python
> 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](https://en.wikipedia.org/wiki/CAR_and_CDR)* 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.

```python
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:

```python
>>> 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:

```python
>>> 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`:

```python
>>> 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:

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

```

```python
>>> 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!