How does reduce function work?

Question

As far as I understand, the reduce function takes a list l and a function f. Then, it calls the function f on first two elements of the list and then repeatedly calls the function f with the next list element and the previous result.

So, I define the following functions:

The following function computes the factorial.

def fact(n):
    if n == 0 or n == 1:
        return 1
    return fact(n-1) * n


def reduce_func(x,y):
    return fact(x) * fact(y)

lst = [1, 3, 1]
print reduce(reduce_func, lst)

Now, shouldn't this give me ((1! * 3!) * 1!) = 6? But, instead it gives 720. Why 720? It seems to take the factorial of 6 too. But, I need to understand why.

Can someone explains why this happens and a work-around?

I basically want to compute the product of factorials of all the entries in the list. The backup plan is to run a loop and compute it. But, I would prefer using reduce.

Answer 1

The other answers are great. I'll simply add an illustrated example that I find pretty good to understand reduce():

>>> reduce(lambda x,y: x+y, [47,11,42,13])
113

will be computed as follows:

(Source) (mirror)

Answer 2

The easiest way to understand reduce() is to look at its pure Python equivalent code:

def myreduce(func, iterable, start=None):
    it = iter(iterable)
    if start is None:
        try:
            start = next(it)
        except StopIteration:
            raise TypeError('reduce() of empty sequence with no initial value')
    accum_value = start
    for x in it:
        accum_value = func(accum_value, x)
    return accum_value

You can see that it only makes sense for your reduce_func() to apply the factorial to the rightmost argument:

def fact(n):
    if n == 0 or n == 1:
        return 1
    return fact(n-1) * n

def reduce_func(x,y):
    return x * fact(y)

With that small revision, the code produces 6 as you expected :-)

>>> lst = [1, 3, 1]
>>> myreduce(reduce_func, lst)
6

Answer 3

Your function calls fact() on both arguments. You are calculating ((1! * 3!)! * 1!). The workaround is to only call it on only the second argument, and pass reduce() an initial value of 1.

Answer 4

From the Python reduce documentation,

reduce(function, sequence) returns a single value constructed by calling the (binary) function on the first two items of the sequence, then on the result and the next item, and so on.

So, stepping through. It computes reduce_func of the first two elements, reduce_func(1, 3) = 1! * 3! = 6. Then, it computes reduce_func of the result and the next item: reduce_func(6, 1) = 6! * 1! = 720.

You missed that, when the result of the first reduce_func call is passed as input to the second, it's factorialized before the multiplication.

Answer 5

Ok, got it:

I need to map the numbers to their factorials first and then call reduce with multiply operator.

So, this would work:

lst_fact = map(fact, lst)
reduce(operator.mul, lst_fact)

Answer 6

Well, first of all, your reduce_func doesn't have the structure of a fold; it doesn't match your description of a fold (which is correct).

The structure of a fold is: def foldl(func, start, iter): return func(start, foldl(func, next(iter), iter)

Now, your fact function doesn't operate on two elements - it just calculates factorial.

So, in sum, you're not using a fold, and with that definition of factorial, you don't need to.

If you do want to play around with factorial, check out the y-combinator: http://mvanier.livejournal.com/2897.html

If you want to learn about folds, look at my answer to this question, which demonstrates its use to calculate cumulative fractions: creating cumulative percentage from a dictionary of data

Answer 7

You could also implement factorial using reduce.

def factorial(n):
  return(reduce(lambda x,y:x*y,range(n+1)[1:]))

Answer 8

Reduce executes the function in parameter#1 successively through the values provided by the iterator in parameter#2

print '-------------- Example: Reduce(x + y) --------------'

def add(x,y): return x+y
x = 5
y = 10

import functools
tot = functools.reduce(add, range(5, 10))
print 'reduce('+str(x)+','+str(y)+')=' ,tot

def myreduce(a,b):
    tot = 0
    for i in range(a,b):
        tot = tot+i
        print i,tot
    print 'myreduce('+str(a)+','+str(b)+')=' ,tot

myreduce(x,y)

print '-------------- Example: Reduce(x * y) --------------'

def add(x,y): return x*y
x = 5
y = 10

import functools
tot = functools.reduce(add, range(5, 10))
print 'reduce('+str(x)+','+str(y)+')=' ,tot

def myreduce(a,b):
    tot = 1
    for i in range(a,b):
        tot = tot * i
        print i,tot
    print 'myreduce('+str(a)+','+str(b)+')=' ,tot

myreduce(x,y)

Answer 9

Beyond the trivial examples, here is one where I find reduce to be actually quite useful:

Imagine an iterable of ordered int values, often with some runs of contiguous values, and that we'd like to "summarize" it as a list of tuples representing ranges. (Note also that this iterable could be a generator of a very long sequence --another reason to use reduce and not some operation on an in-memory collection).

from functools import reduce

def rle(a, b):
    if a and a[-1][1] == b:
        return a[:-1] + [(a[-1][0], b + 1)]
    return a + [(b, b + 1)]

reduce(rle, [0, 1, 2, 5, 8, 9], [])
# [(0, 3), (5, 6), (8, 10)]

Notice the use of a proper initial value ([] here) for reduce.

Corner cases handled as well:

reduce(rle, [], [])
# []

reduce(rle, [0], [])
# [(0, 1)]