reduce begins to unlock some serious power from Python's standard library. Here's a dead-simple example of summing a list using reduce:

1from functools import reduce
2res = reduce(lambda acc, v: acc + v, [1,2,3,4,5])
3print(res) # 15

This is what's happening:

In ascii, you might draw the table like this:

1res   acc   v
2      1     2     [|1|,|2|, 3 , 4 , 5 ]
3      3     3     [ 1 , 2 ,|3|, 4 , 5 ]
4      6     4     [ 1 , 2 , 3 ,|4|, 5 ]
5      10    5     [ 1 , 2 , 3 , 4 ,|5|]
615

Remember that drawing these tables in ascii is a very quick way of gaining a complete understanding of whatever number crunching you are doing, and is probably the most effective and quickest method of all.

The lambda passed into reduce takes two arguments, i like calling the first one the accumulator and the second one the value. Initially they take the first two values of the list. After adding 1 + 2, the resulting 3 of that addition gets passed in to the acc, so the next computation is 3 + 3, then 6 + 4 and so on.

Of course, we could use a second lambda to implement an actual sum function:

1from functools import reduce
2sum = lambda A: reduce(lambda acc, v: acc + v, A)
3print(sum([1,2,3,4,5])) # 15

Alternatively we could use operator.add and operator.mult to implement sum and product functions.

1from functools import reduce
2from operator import add, mul
3sum =  lambda A: reduce(add, A)
4prod = lambda A: reduce(mul, A)
5print(sum([1,2,3,4,5])) # 15
6print(prod([1,2,3,4,5])) # 120

Starting value

On the first iteration, reduce uses the first two numbers in A for the values of a and b in the lambda. In some cases, you'll want to control the initial value of a using reduce's third argument, while b receives the first value of A:

1from functools import reduce
2sum =  lambda A: reduce(add, A, 0)
3print(sum([1,2,3,4,5])) # 15

You'll soon see why this can be incredibly useful.

Find the missing number in array

Q: Given a list of numbers from 0 -> n missing 1 number, find the missing number in O(1) space and O(n) time. (leetcode link).

Solution:

Taking the xor of all the numbers in the array we're given, and taking the xor of all the numbers in range(n + 1) and xoring these two results together gives us the missing number:

1from functools import reduce
2from operator import ixor
3
4find_missing = lambda A: ixor(reduce(ixor, A), reduce(ixor, range(len(A) + 1)))
5find_missing([5, 1, 2, 3, 4, 0, 6, 7, 8, 10]) # result 9

Roman Numerals

Here's how to solve the roman numeral to integer problem using reduce: the key difficulty is that if the current number, e.g I is less than the following number V it has to be subtracted, not added.

Let's begin by initialising our roman to int lookup dictionary, using the dict constructor. When keys don't start with a number, and doesn't contain inconvenient characters, using dict can be very hand and compact.

1from functools import reduce
2S = dict(I=1, V=5, X=10, L=50, C=100, D=500, M=1000)

Next, let's take a look at our reduce. Let's ignore the lambda for now. The sequence we're passing in is the range(len(s)-1), so in the case of XIV: the sequence [1,0]. The third value we pass into reduce is that actual integer value of the last character (5).

1reduce(lambda a, b: None, reversed(range(len(s)-1)), S[s[-1]])

 1from functools import reduce
 2from operator import add, sub
 3
 4S = dict(I=1, V=5, X=10, L=50, C=100, D=500, M=1000)
 5
 6def romanToInt(s):
 7    def func(a, b):
 8        if S[s[b+1]] > S[s[b]]:
 9            return a - S[s[b]]
10        else:
11            return a + S[s[b]]
12    return reduce(func, reversed(range(len(s)-1)), S[s[-1]])
13
14print(romanToInt('XIV')) # 14

 1from functools import reduce
 2from operator import add, sub
 3
 4S = dict(I=1, V=5, X=10, L=50, C=100, D=500, M=1000)
 5
 6def romanToInt(s):
 7    r = lambda a, b: (add, sub)[S[s[b+1]] > S[s[b]]](a, S[s[b]])
 8    return reduce(r, reversed(range(len(s)-1)), S[s[-1]])
 9
10print(romanToInt('XIV')) # 14