20.35. reduce(): Sequence reduction

20.35. `reduce()`: Sequence reduction

The idea of reduction comes from the world of functional programming. There is a good introductory article on this concept in Wikipedia. In simple terms, a function of two arguments is applied repeatedly to the elements of an iterable to build up a final value.

The idea of a “sum of elements of a sequence” is a reduction of those elements using “+” as the function. For example, the +-reduction of [2, 3, 5] is 2+3+5 or 10.
Similarly, the product of a series of numbers is a reduction using the “*” operator: the multiply reduction of [2, 3, 5] is 2*3*5 or 30.

There are two general forms:

reduce(f, S)
reduce(f, S, I)

f is a function that takes two arguments and returns a value.
S is an iterable.

The result depends on the number of elements in S, and whether the initial value I is supplied. Let's look first at the case where argument I is not supplied.

If S has only one element, the result is S[0].
If S has two elements, the result is f(S[0], S[1]).
If S has three elements, the result is f(f(S[0], S[1]), S[2]).
If S has four or more elements, f is applied first to S[0] and S[1], then to that result and S[2], and so on until all elements are reduced to a single value.
If S is empty and no initial value was provided, the function raises a TypeError exception.

If an initial value I is provided, the result is the same as reduce(f, [I]+list(S)).

Some examples:

>>> def x100y(x,y):
...     return x*100+y
... 
>>> reduce(x100y, [15])
15
>>> reduce(x100y, [1,2])
102
>>> reduce(x100y, [1,2,3])
10203
>>> reduce(x100y, (), 44)
44
>>> reduce(x100y, [1], 2)
201
>>> reduce(x100y, [1,2], 3)
30102
>>> reduce(x100y, [1,2,3], 4)
4010203
>>> reduce(x100y, [])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: reduce() of empty sequence with no initial value

Python 2.7 quick reference

20.35. reduce(): Sequence reduction

20.35. `reduce()`: Sequence reduction