Introduction to Functional Programming with Python

We now come back to higher order functions. I will present map, filter and reduce. Like sorted, these functions take a function and an iterator as parameters.

When we work with collections, two very common programming patterns emerge:

1. iterating a collection to build another collection. In this case, at each iteration, we want to apply some transformation or some test to the current item and append the result to the new collection. map, filter and sorted fall into this category.
2. iterating a collection and accumulating intermediate results to build a single value. any, all, len, min, max and sum fall into this category. In this section, we will study reduce which is a generalized version of these specific functions. As an exercise, you will use reduce to write your own version of these functions.

Converting the items of a collection with map.

map creates a new collection by applying a function to each item of the source collection. To get the 10 first even numbers, with map you can write: evens = map(lambda n: n*2, range(10)).

map returns an iterator. The good point is that it saves memory. The bad point is that it can be iterated only once. If you need to iterate the collection several times, or access items by index, then create a list out of the iterator: evens = list(map(lambda n: n*2, range(20))).

Most of the time, you can use a generator expression instead of a call to map. Which one to use is up to your preferences. If you have to define a function inline using lambda, then I think a generator expression will be a bit more clearer than a call to map. However, if the mapping function already exists then I prefer a call to map. Compare for yourself:

# we reuse the class BonusChest of the introduction
wealthUsingMap = sum(map(BonusChest.getNumCoins, myChests))
wealthUsingGen = sum(chest.getNumCoins() for chest in myChests)

Filtering collections with filter

filter applies a function to each item of the source collection and creates a new one by keeping the items for which this function returns true.

Again, to get the 10 first even numbers, with filter you can write: evens = filter(lambda n: n%2==0, range(20)).

Like map, most of the time you can replace a call to filter by a generator expression: evens = (n for n in range(20) if n%2 == 0). But, if you have the filtering function at hand, filter gives very readable code: evens = filter(isEven,range(20)).

Aggregating a collections to a single value with reduce

In this section, we will study reduce and we will also try to learn some functional thinking: how can we convert imperative code to functional code ? We will rely on the factorial function as our supporting example.

reduce takes 3 arguments:

1. an accumulating function which takes 2 arguments : (1) the current accumulated value; (2) the current item. It return the final accumulated value.
2. an iterator which contains the values to be accumulated;
3. an initial value for the accumulated value. reduce returns the final accumulated value.

From an imperative factorial to a functional one

In an imperative manner, you would compute factorial(10) in the following way:

def factorial(n):
    fact = 1
    for currentValue in range(1,n):
        fact = fact*currentValue
    return fact
fact10 = factorial(10) 

So, how do we rewrite this function in a functional style? We saw that functional programming relies on collections. Here Python is easy with us, since the for loop goes through an iterator. For factorial, the handled collection is range(1,n), which represents all the numbers we want to multiply. Next, we see that the imperative factorial function returns a single value, so we can probably implement it with our second programming pattern: it processes a collection and returns a single value. Now, we see that the fact variable is used as an accumulator: at each iteration it is multiplied by the current item. This clearly corresponds to the second kind programming pattern, so we should be able to replace the body of factorial by a call to reduce.

For factorial, the accumulating function is the multiplication. Thus, we have our first argument and can write reduce(mult,?,?). We suppose here that we have a mult function at hand. We found that the accumulated collection is range(1,n), so we can fill in the second argument: reduce(mult,range(1,n),?). We just need the start value to complete our call. It's of course 1 for factorial, but you can also find it by searching the accumulator variable in the imperative version and lookup its initial value. The complete call is: reduce(mult,range(1,n),1).

Here is the full function factorial function:

from functools import reduce
from operator import mult

def factorial(n):
	return reduce(mult,range(1,n),1)
    
fact10 = factorial(10) 

Let's now analyse the two import calls that we used in the functional factorial. Starting from Python 3, you must import reduce from the functools module. In Python 2, reduce was a built-in function and was always available. Even if reduce is not a built-in function per-se, we cannot skip it ; we would loose a whole part of the functional programming fun. reduces is really the buddy of map and filter. See for example the MapReduce of Google.

Next, we import the mult function from the operator module. This module contains many utility functions which are particularly handy with higher order functions. They spare you from writing small lambda functions for common operations, such as arithmetic operations, boolean operations, attribute access...

Some subjective functional programming advocacy

Of course you do not need to always write the imperative version and convert it to the functional version. However, taking a piece of existing code and trying to make it functional is a good exercise. You can apply the same method we used for factorial: (1) identify the collection ; (2) does the code rely on one of our two the functional patterns ? ; (3) which function will you use ? After some time and with practice, you will start to think functionally and skip the imperative version.

A benefit of functional programming is that it simplifies the reading of programs. When reading from left to right, you read first the outer function, which gives the general scope of the operation. Arguments gives you the details. Let's see how this applies to a our reduce call. When you see reduce, you know that we will process an iterator and generate a value. This is our second functional pattern. Then, you read the accumulating operation, mult in our example. So, at this point, we know that we will perform a sequence of multiplication and return the final value. The next argument tells us what is the sequence of multiplied numbers. The final argument tells from where we start. On the contrary, when you see the imperative version, you have to work out the details, such as analyzing how the loop updates the variables, to extract the general algorithm.

If you compare the two versions of factorial, you will see that reduce:

1. gives us a more compact code, without sacrificing readability;
2. is less error prone, because it does not rely on an intermediate variable that you have to declare, initialize and maintain in the for loop.

Please, stay in readable code territory

reduce really shines if you can avoid defining a lambda. Without the operator module we would write:

from functools import reduce

def factorial(n):
    return reduce(lambda accValue,curItem:accValue*curItem,range(1,n),1)

This version is arguably not very readable and should be avoided. In that case, I would advise to skip the lambda function and to define the mult function yourself:

from functools import reduce

def factorial(n):
    def mult(a,b): return a*b
    return reduce(mult,range(1,n),1)

Hands on session

reduce and map are so fundamental to functional programming that you cannot avoid coding your own version. So this is your time!

The next exercise will illustrate how general reduce is. You have now to implement any, all, sum, min and max by calling reduce. For the sake of simplicity, you can consider that max and min receive a list of int comprised between 0 and 1000.