The Reduce Function is Dead. Long Live the Reduce Function!

This article is a first section draft of my upcoming Python book “Python One-Liners” (to appear with NoStarchPress in 2020). I thought I’d share it because recently I published an article about the fate of the reduce function in Python that got a lot of attention in the Python community. While the recently published article showcases the disadvantages of the reduce function, this article is really a love declaration. So enjoy studying the power of the reduce function to write concise Python one-liners.

How to Write Python One-Liners with the Reduce Function

In Python version 2, the reduce function was built-in so you could simply use it without importing any external library. However, Python’s creator Guido van Rossum pushed towards removing it in Python 3. In a now famous article, he made his position clear: the reduce function is seldom used and doesn’t provide much value to the average Python coder. Therefore, in Python 3, you need to import it first from the functools library.

Anyways, a minority of Python experts still enjoys using the powerful reduce function in unexpected and beautiful ways. When researching this function as a preparation for this book, I realized that there exists a pop-culture of “Python hackers” around the reduce function and its unintended uses. And in fact, to create powerful Python one-liners, the reduce function is of invaluable help!

You may need to invest some time to understand it though. The reduce function takes three arguments: reduce(function, iterable, initializer). The function argument defines how two values x and y are reduced to a single value (for example, lambda x, y: x + y). This way, we can iteratively reduce two values of an iterable (the second argument) to a single value—until only a single value is left in the iterable.

For example, calling reduce(lambda x, y: x + y, [0, 1, 2, 3]) performs the following computation: (((0+1)+2)+3)=6. In other words, we first reduce the two values x=0 and y=1 to the sum x+y=0+1=1. Then, we use this result of the first call of the lambda function as input to the second call of the lambda function: x=1 and y=2. The result is the sum x+y=1+2=3. Finally, we use the result of this second call of the lambda function as input to the third call of the lambda function by setting x=3 and y=3. The result is the sum x+y=3+3=6. In the last example, you have seen that the value x always carries the result of the previous (lambda) function. The argument x serves as the accumulated value while the argument y serves as the update value from the iterable. This is the intended behavior to iteratively “reduce” all values in the iterable argument to a single one. The optional third parameter initializer specifies the initial input for x.

How to Calculate the Powerset in One-Line of Python Code?

We’ll create a one-liner solution that calculates the powerset of a given set s:

# Dependencies
from functools import reduce

# The Data
s = {1, 2, 3}

# The One-Liner
ps = lambda s: reduce(lambda P, x: P + [subset | {x} for subset in P], s, [set()])

# The Result

Before we move on, guess the output of this code snippet!

How The One-Liner Works

The idea of this one-liner is to start the powerset as an empty set and repeatedly add subsets to it until no more subsets can be found.

Initially, the powerset contains only the empty set. In each step, we take one element x out of the dataset s and create new subsets that naturally emerge by adding x to all subsets that are already in the powerset. The size of the powerset therefore doubles each time we consider an additional element x from the dataset s. In this way, we can grow the powerset with n subsets one data set element at-a-time (but by n subsets at-a-time). Note that the powerset grows exponentially: for any new data set element x, we double the size of the powerset. This is an inherent property of powersets: they quickly overwhelm any storage capacity—even for relatively small datasets with only a few dozen of elements.

We use the reduce() function to maintain the current powerset in the variable P (which initially contains only the empty set). Using list comprehension, the reduce function creates new subsets – one for each existing subset – and adds them to the powerset P. In particular, it adds the value x from the dataset to each subset and thus doubles the size of the powerset (containing the subsets with and without the dataset element x). In this way, the reduce function repeatedly “merges” two elements: the powerset P and an element x from the dataset.

Hence, the result of the one-liner is the following:

# The Result
# [set(), {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}]

This one-liner nicely demonstrates how important it is that you have a thorough understanding of the basics such as lambda functions, list comprehension, and set operations.

Leave a Comment

Your email address will not be published. Required fields are marked *