Map, filter, and reduce — Python: Functions

• The map function
• The filter function
• The reduce function
• The higher-order functions versus for loops

In this lesson, we will look at three examples of higher-order functions. Programmers use these functions in many languages. It is worth noting up front that the examples in this lesson are somewhat simplified. We will discuss the Python versions of these functions.

For greater flexibility and performance, we implement them slightly differently. Simple examples can successfully demonstrate the purpose and general principle of operation.

The map function

When working with lists, we often have to apply some form of transformation (specifically, the same kind of transformation) for each element. Of course, we can always write a loop. However, this loop will look identical in almost all cases:

def f(x):
    …

new_list = []
for item in old_list:
    new_item = f(item)
    new_list.append(new_item)

# …
# Using `new_list`

In such cases, only the applied f function changes. So why not generalize this code so that the function is a parameter? That is what we are going to do:

def map(function, items):
    result = []
    for item in items:
        result.append(function(item))
    return result
map(str, range(5))
# ["0", "1", "2", "3", "4"]

The function is called map. The name comes from mathematics. We give the same name to functions that map one set of values to another by converting all elements using some transformation. Most languages use the same name.

The filter function

Often you do not need to transform the elements so much as you need to keep some of them in the list and discard others according to some criterion. A filter function solves this problem in many languages. The code for this function looks similar to the map code:

def filter(predicate, items):
    result = []
    for item in items:
        if predicate(item):
            result.append(item)
    return result

def is_odd(x):
    return x % 2

filter(is_odd, range(6))
# [1, 3, 5]

Our filter function applies a predicate to each element and adds elements to the output list only if the predicate returns True. The filter function has a more descriptive name but is just as popular. Many languages have a similar function with the same name.

The reduce function

Both map and filter work on single elements independently. But there are also loops that aggregate the result, forming a single result argument by combining elements using an accumulator argument.

A typical example of aggregation might be the sum of all items in a list. Or, say, a work. Suppose we want to add all the items in the list:

[1,2,3,4,5]

Mathematically, the sum looks like that:

1 + 2 + 3 + 4 + 5

We can express it like this:

(((((0 + 1) + 2) + 3) + 4) + 5)

Zero here is the same accumulator, the initial state. It does not add anything to the total, but it can serve as a starting point. And it will serve as the result if the input list is empty. If we use a loop, we would add things up like this:

acc = 0
for item in items:
    acc = acc + item

And multiply them like this:

acc = 1
for item in items:
    acc = acc * item

Notice a trend? The loops differ only in:

• The initial value of the accumulator (0 and 1)
• The operation that combines the element and accumulator (+and *)

Let us summarize:

def reduce(operation, initial_value, items):
    acc = initial_value
    for item in items:
        acc = operation(acc, item)
    return acc

from operator import add, mul
reduce(add, 0, [1, 2, 3, 4, 5])
# 15
reduce(mul, 1, [1, 2, 3, 4, 5])
# 120

In the example, we used the add and mul from the operator module. These are equivalents of + and * that we can use in conjunction with higher-order functions. The reduce function is not as lucky with its name as the previous two. We could call this function inject, reduce, and aggregate.

Only in mathematics is everything unambiguous. This kind of function is left fold. And the name is telling: when we use this function, we fold the list into one value. Our fold is left because we start folding the elements with the accumulation on the left. There is also a right fold, but it is not a built-in function in Python.

The right fold for the sum looks like this:

(1 + (2 + (3 + (4 + (5 + 0)))))

In most cases, both folds give the same result if the applied operation is associative — it allows you to place brackets however you want, as is the case for sums. But if you iterate through elements using a loop, it is easier to implement the left fold, which we use more often.

The higher-order functions versus for loops

We have implemented three full functions with less power than the for loop. In addition, the for loop allows you to flexibly manage the iteration process using the break and continue commands.

So why do we need these separate, weaker versions when there is a universal one? These functions do one job, which makes thinking, reading, and writing code much more straightforward.

As soon as we look at the function, we can understand that filter filters and map maps. Moreover, filter does not change the elements because of how we do it, just discarding some of them. And map changes the value of the items but does not change their number or position. Knowing what the code cannot do is worth a lot.

If we had a for loop, we would have to execute the code we have to interpret because the for loop can do everything:

• Change elements
• Discard them
• Aggregate the result
• Do everything simultaneously

Of course, we cannot replace every use of the for loop with a function. But in those simple cases where it is possible to achieve the desired result using a less powerful and easier-to-understand tool, it is worth at least thinking about this alternative.