We now come back to higher order functions. I will present
sorted, these functions take a function and an iterator as parameters.
When we work with collections, two very common programming patterns emerge:
- 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.
sortedfall into this category.
- iterating a collection and accumulating intermediate results to build a single value.
sumfall into this category. In this section, we will study
reducewhich is a generalized version of these specific functions. As an exercise, you will use
reduceto write your own version of these functions.
Converting the items of a collection with
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 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)).
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
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:
- an accumulating function which takes 2 arguments : (1) the current accumulated value; (2) the current item. It return the final accumulated value.
- an iterator which contains the values to be accumulated;
- an initial value for the accumulated value.
reducereturns 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
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:
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
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
- gives us a more compact code, without sacrificing readability;
- 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
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
max by calling reduce. For the sake of simplicity, you can consider that
min receive a list of int comprised between 0 and 1000.