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.
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,
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
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
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.
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
b that are defined on the outer scope (at the
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
However, we can also see two more things:
pairitself receives a function,
fas 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.
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 = 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 >>>
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!