reduce: the narrow band where it earns its place

functools.reduce(function, iterable[, initial]) folds a binary function over a sequence. It moved out of builtins in Python 3 because, in Guido’s judgment, it is usually less readable than the loop it replaces — and because for almost every common fold there is a named function that says what it means.

The replacements, in order of how often they apply

Fold	Write
sum	`sum(xs)`
product	`math.prod(xs)`
minimum / maximum	`min(xs)` / `max(xs)`
any / all true	`any(xs)` / `all(xs)`
concatenate strings	`"".join(parts)`
concatenate lists	`list(chain.from_iterable(lists))`
merge dicts	`{k: v for d in ds for k, v in d.items()}`

Each of those is faster, clearer, and — this is the point — impossible to get accidentally quadratic.

The quadratic trap

reduce(operator.add, list_of_lists)

Each + builds a new list containing everything accumulated so far. Over $n$ lists of average length $m$ that is $O(n^2 m)$ time and $O(n^2 m)$ total allocation. chain.from_iterable is $O(nm)$.

The same shape catches string concatenation (reduce(operator.add, strings) against "".join(strings)) and dict merging. The tell is always the same: the accumulator type is a container, and the operator copies it. If combining two accumulated values costs proportional to their size, folding is quadratic.

💡sum(list_of_lists, []) works and is also quadratic. Python 3.12 click to reveal

makes sum of strings a TypeError outright. Why the asymmetry? Because the string case was overwhelmingly a mistake and the list case is sometimes deliberate.

sum(strings, "") is quadratic and there has always been an obviously correct one-liner ("".join), so refusing it costs nobody anything and saves a common performance bug. CPython special-cases it with a TypeError that names join in the message.

For lists there is no equally-obvious builtin — chain.from_iterable requires an import and is not what a beginner reaches for — and flattening three small lists with sum(lists, []) is harmless. So it stays legal, and stays quadratic, and stays a thing to catch in review when the list count is not small.

The general lesson: “it works on my fixture” and “it is not quadratic” are independent properties, and only one of them is tested by your test suite.

The narrow band where reduce is right

An associative combination over a non-numeric type, with no named equivalent. Merging bitmasks (reduce(operator.or_, flags)), composing functions, intersecting many sets (reduce(set.intersection, sets)), combining Counters. In each of these the combine operation is genuinely a binary fold, the accumulator is cheap to combine, and there is no builtin.

Even there, an explicit loop is usually just as short and reads in the direction people read. The honest test is whether the fold is the domain concept — “the intersection of all these sets” — or whether it is mechanism you are dressing up.

Typing

The two-argument form solves the accumulator type from the element type, so it requires the function to be Callable[[T, T], T] — a homogeneous fold.

The three-argument form takes the accumulator type from initial, which makes it the only version that type-checks cleanly for a heterogeneous fold — building a dict from a list of pairs, say, where the accumulator and the element are different types.

And initial is not just a typing nicety:

reduce(operator.add, [])
# TypeError: reduce() of empty iterable with no initial value

Without initial, an empty input raises at runtime, and the checker cannot see it — the signature says nothing about emptiness. If the iterable comes from a filter, a query, or a user, pass initial.

⚠ 3.14 deprecates passing function and sequence as keyword arguments (reduce(function=f, sequence=xs)), with removal scheduled for 3.16. Pass them positionally.

💡You are combining a list of Counters. sum(counters, Counter()) click to reveal

and reduce(operator.add, counters, Counter()) are both quadratic-ish. What is the right answer? Neither: use in-place accumulation.

total: Counter[str] = Counter()
for counter in counters:
    total.update(counter)

Counter.__add__ builds a new Counter containing the union of both key sets, so folding it allocates a fresh mapping per step whose size grows toward the final answer. update mutates in place and allocates only for genuinely new keys.

This is the general escape from the quadratic fold, and it applies to lists (extend), dicts (update), sets (|=) and strings (a list plus one join): when the accumulator is a mutable container, mutate it. The functional fold is the wrong shape not because it is functional but because the combine step is $O(\text{size of accumulator})$ rather than $O(\text{size of element})$.