Functional Programming Tools: filter and reduce

The map function is the simplest representative of a class of Python built-ins used for functional programming—tools that apply functions to sequences and other iterables. Its relatives filter out items based on a test function (filter) and apply functions to pairs of items and running results (reduce). Because they return iterables, range and filter both require list calls to display all their results in 3.0. For example, the following filter call picks out items in a sequence that are greater than zero:

>>> list(range(−5, 5))                                   # An iterator in 3.0
[−5, −4, −3, −2, −1, 0, 1, 2, 3, 4]

>>> list(filter((lambda x: x > 0), range(−5, 5)))        # An iterator in 3.0
[1, 2, 3, 4]

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

Items in the sequence or iterable for which the function returns a true result are added to the result list. Like map, this function is roughly equivalent to a for loop, but it is built-in and fast:

>>> res = []
>>> for x in range(−5, 5):
...     if x > 0:
...         res.append(x)
...
>>> res
[1, 2, 3, 4]

reduce, which is a simple built-in function in 2.6 but lives in the functools module in 3.0, is more complex. It accepts an iterator to process, but it’s not an iterator itself—it returns a single result. Here are two reduce calls that compute the sum and product of the items in a list:

>>> from functools import reduce      # Import in 3.0, not in 2.6

>>> reduce((lambda x, y: x + y), [1, 2, 3, 4])
10
>>> reduce((lambda x, y: x * y), [1, 2, 3, 4])
24

At each step, reduce passes the current sum or product, along with the next item from the list, to the passed-in lambda function. By default, the first item in the sequence initializes the starting value. To illustrate, here’s the for loop equivalent to the first of these calls, with the addition hardcoded inside the loop:

>>> L = [1,2,3,4]
>>> res = L[0]
>>> for x in L[1:]:
...     res = res + x
...
>>> res
10

Coding your own version of reduce is actually fairly straightforward. The following function emulates most of the built-in’s behavior and helps demystify its operation in general:

>>> def myreduce(function, sequence):
...     tally = sequence[0]
...     for next in sequence[1:]:
...         tally = function(tally, next)
...     return tally
...
>>> myreduce((lambda x, y: x + y), [1, 2, 3, 4, 5])
15
>>> myreduce((lambda x, y: x * y), [1, 2, 3, 4, 5])
120

The built-in reduce also allows an optional third argument placed before the items in the sequence to serve as a default result when the sequence is empty, but we’ll leave this extension as a suggested exercise.

If this coding technique has sparked your interest, you might also be interested in the standard library operator module, which provides functions that correspond to built-in expressions and so comes in handy for some uses of functional tools (see Python’s library manual for more details on this module):

>>> import operator, functools
>>> functools.reduce(operator.add, [2, 4, 6])        # Function-based +
12
>>> functools.reduce((lambda x, y: x + y), [2, 4, 6])
12

Together with map, filter and reduce support powerful functional programming techniques. Some observers might also extend the functional programming toolset in Python to include lambda, discussed earlier, as well as list comprehensions—a topic we will return to in the next chapter.