List comprehension as substitute for reduce() in Python

Question

The following python tutorial says that:

List comprehension is a complete substitute for the lambda function as well as the functions map(), filter() and reduce().

http://python-course.eu/python3_list_comprehension.php

However, it does not mention an example how a list comprehension can substitute a reduce() and I can't think of an example how it should be possible.

Can please someone explain how to achieve a reduce-like functionality with list comprehension or confirm that it isn't possible?

Answer 1

You could accomplish something like a reduce with a comprehension by using a couple of helper functions that I've named last and cofold:

>>> last(r(a+b) for a, b, r in cofold(range(10)))
45

This is functionally equivalent to

>>> reduce(lambda a, b: a+b, range(10))
45

Note that unlike reduce() the comprehension didn't use a lambda.

The trick is to use a generator with a callback to "return" the result of the operator. cofold is the corecursive dual of the reduce (or fold) function.

_sentinel = object()
def cofold(it, initial=_sentinel):
    if initial is _sentinel:
        it = iter(it)
        accumulator = next(it)
    else:
        accumulator = initial
    def callback(result):
        nonlocal accumulator 
        accumulator = result
        return result
    for element in it:
        yield accumulator, element, callback

Here's cofold in a list comprehension.

>>> [r(a+b) for a, b, r in cofold(range(10))]
[1, 3, 6, 10, 15, 21, 28, 36, 45]

The elements represent each step in the dual reduction. The last one is our answer. The last function is trivial.

def last(it):
    for e in it:
        pass
    return e

Unlike reduce, cofold is a lazy generator, so it can safely act on infinite iterables when used in a generator expression.

>>> from itertools import islice, count
>>> lazy_results = (r(a+b) for a, b, r in cofold(count()))
>>> [*islice(lazy_results, 0, 9)]
[1, 3, 6, 10, 15, 21, 28, 36, 45]
>>> next(lazy_results)
55
>>> next(lazy_results)
66

Answer 2

List comprehensions are supposed to return lists. If your reduce is supposed to return a list, then yes, you can replace it with a list comprehension.

But this is no obstacle to providing "reduce-like functionality". Python lists can contain any object. If you'll accept your result contained in a single-item list, then there is a [...][0] list comprehension form that can replace any reduce() whatsoever.

This should be obvious, but that form is

[x for x in [reduce(function, sequence, initial)]][0]

for some binary function and and some iterable sequence and some initial value. Or, if you want the initial from the first of the iterable,

[x for x in [reduce(function, sequence)]][0]

---

Arguably, the above is cheating, and also pointless, since you could just use reduce without the comprehension. So let's try it without reduce.

[stack.append(function(stack.pop(), e)) or stack[0]
 for stack in ([initial],)
 for e in sequence][-1]

This produces a list of all the intermediate values, and we want the last one. [-1] is just as easy as [0]. We need an accumulator to reduce, but can't use assignment statements in a comprehension, hence the stack (which is just a list), but we could have used many other data structures here. The .append() always returns None, so we use or stack[0] to put the value so far in the resulting list.

It's a little more difficult without initial,

[stack.append(function(stack.pop(), e)) or stack[0]
 for it in [iter(sequence)]
 for stack in [[next(it)]]
 for e in it][-1]

Really, you might as well use a for statement at this point.

---

But this takes up memory for the list of intermediate values. For a very long sequence, that might be a problem. But we can avoid that too by using generator expressions.

Doing this is tricky, so let's start with an easier example and work up to it.

stack = [initial]
[stack.append(function(stack.pop(), e)) for e in sequence]
stack.pop()  # returns the answer

It computes the answer, but also creates a useless list of Nones. We can avoid that by converting it to a generator expression inside a list comprehension.

stack = [initial]
[_ for _s in (stack.append(function(stack.pop(), e)) or ()
              for e in sequence)
 for _ in _s]
stack.pop()

The list comprehension exhausts the generator that updates the stack, but returns an empty list itself. This is possible because the inner loop always has zero iterations, because _s is always an empty tuple.

We can move the stack.pop() inside if the last _s has one element. It doesn't matter what that element is though. So we chain on a [None] as the final _s.

from itertools import chain
stack = [initial]
[stack.pop()
 for _s in chain((stack.append(function(stack.pop(), e)) or ()
                  for e in sequence),
                 [[None]])
 for _ in _s][0]

Again, we have a single-item list comprehension. We can also implement chain as a generator expression. And you've already seen how to move the stack variable inside using a single-item list.

[stack.pop()
 for stack in [[initial]]
 for _s in (
         x
         for xs in [
                 (stack.append(function(stack.pop(), e)) or ()
                  for e in sequence),
                 [[None]],
         ]
         for x in xs)
 for _ in _s][0]

And we can also get the initial from the sequence for the two-argument reduce.

[stack.pop()
 for it in [iter(sequence)]
 for stack in [[next(it)]]
 for _s in (
         x
         for xs in [
                 (stack.append(function(stack.pop(), e)) or ()
                  for e in it),
                 [[None]],
         ]
         for x in xs)
 for _ in _s][0]

This is insane. But it works. So yes, it's possible to get "reduce-like functionality" with comprehensions. That doesn't mean you should. Seven fors is too hard!

Answer 3

I was surprised at first to find that Guido van Rossum, creator of Python, was against reduce. His reasoning was that beyond summing, multiplying, and-ing, and or-ing, using reduce yields an unreadable solution that is better suited by a function which iterates through and updates an accumulator. His article on the matter is here. So no, there isn't a list comprehension alternative to reduce, instead the "pythonic" way is to implement an accumulating function the old fashioned way:

Instead of:

out = reduce((lambda x,y: x*y),[1,2,3])

Use:

def prod(myList):
    out = 1
    for el in myList:
        out *= el
    return out

Of course nothing stops you from continuing to use reduce (python 2) or functools.reduce (python 3)

Answer 4

Ideally, list comprehension is to create a new list. Quoting official documentation,

List comprehensions provide a concise way to create lists. Common applications are to make new lists where each element is the result of some operations applied to each member of another sequence or iterable, or to create a subsequence of those elements that satisfy a certain condition.

whereas reduce is used to reduce an iterable to a single value. Quoting functools.reduce,

Apply function of two arguments cumulatively to the items of sequence, from left to right, so as to reduce the sequence to a single value.

So, list comprehension cannot be used as a drop-in replacement for reduce.