Douglas Alan
Describing reduce() in 10 seconds is utterly trivial to anyone with an
IQ above 100, whether or not they have ever used sum():
"To add a sequence of numbers together:
reduce(add, seq)
To multiply a sequence of numbers together:
reduce(mul, seq)
... Any two-argument function can be used in place of add, mul, sub, or
div and you'll get the appropriate result. Other interesting
examples are left as an exercise for the reader."
This isn't enough to describe what 'reduce' does. For
example, after reading this someone could think that
reduce(add, seq) is a macros which expands to
seq[0] + seq[1] + seq[2] + ...
and that reduce(mul, seq) is the same as
seq[0] * seq[1] * seq[2] + ...
For all the examples you gave, this is correct. However,
reduce(pow, seq) is not the same as
seq[0] ** seq[1] ** seq[2] + ...
because the order of operations is different.
import operator
reduce(operator .pow, [2, 3, 4])
4096 2**3**4
241785163922925 8349412352L (2**3)**4
4096
I would argue that a "better" way to describe 'reduce'
is by defining it through its implementation, as
def reduce(f, seq):
val = seq[0]
for x in seq[1:]:
val = f(val, x)
return val
or by explaining it as
reduce(f, (a, b)) is the same as f(a, b)
reduce(f, (a, b, c)) is the same as f(f(a, b), c)
reduce(f, (a, b, c, d)) is the same as f(f(f(a, b), c), d)
and reduce(f, seq) is the same as
f(...f(f(f(f(se q[0], seq[1]), seq[2]), seq[3]), seq[4]), ....seq[n-1])
As I pointed out, any approach assumes the student knows
what it means to pass a function around. This is not
something that a beginning programmer (the proverbial CS
101 student) necessarily knows or is taught in that course.
(I know that you'll disagree with that statement.)
As others have pointed out, you must at that time explain
when/why 'reduce' is useful, otherwise it is not going to be
remembered, or at best put away on the mental top-shelf
only to be pulled out on rare occasion. For that matter, are
you prepared to answer the question 'why is it called "reduce"?' ?
You've already given an example of when it's useful. You
said that you use it all the time, as in
def longer(x, y):
if len(y) > len(x): return y
else: return x
def longest(seq):
return reduce(longer, seq)
It took me a while but I figured out why it works and
why it's clever. It must have taken so long because of
my substandard CS education. It appears though that
many others in the Python world have suffered from a
poor CS education because there are only six uses of
'reduce' in the top-level of the standard library, (And
several are rather confusing.)
Of those, cvs.py has a tricky way to write
sum( (x[1] for x in items) )
and difflib.py has a way to write
sum( (x[-1] for x in self.get_matchi ng_blocks()) )
and profile.py could also be written as the simpler
def get_time_timer( timer=timer, sum=sum):
return sum(timer())
so 1/2 of those reduce cases are disguised 'sum's.
The other three are in csv.py and look something like
quotechar = reduce(lambda a, b, quotes = quotes:
(quotes[a] > quotes[b]) and a or b,
quotes.keys())
and are identical in intent to your use case -- select the
object from a list which maximizes some f(obj).
This suggests the usefulness of a new function or two,
perhaps in itertools, which applies a function to a list
of values and returns the first object which has the
maximum value, as in
def imax(seq, f = lambda x: x):
seq = iter(seq)
obj = seq.next()
maxobj, maxval = obj, f(obj)
while 1:
try:
obj = seq.next()
except StopIteration:
return maxobj
val = f(obj)
if val > maxval:
maxobj, maxval = obj, val
and an equivalent imin. Note that this is "better" than
your code because f(x) is only computed once per
object or N times total, while you compute it 2*(N-1)
times. In some cases the f(x) may be the most
expensive term in the calculation.
Then your 'longest' could be implemented as
def longest(seq):
return imax(seq, len)
and the example code from csv can be rewritten as
the simpler (IMO, of course):
quotechar = imax(quotes.key s(),
lambda a, quotes = quotes: quotes[a])
I tried looking for places in the std. lib which are better
expressed as a 'reduce' but that was a hard search.
Instead, I looked for places which compute a sum by
using an explicit loop, to see if they are better written in
some alternate form. I looked for places which used the
words 'sum', 'total', or 'tot', as well as places where
there was a '= 0' followed by a '+' within the next few
lines. There were very few, and the paucity suggests
that 'sum' isn't needed all that often. Then again, I'm
not one who suggested that that be a builtin function ;)
In fact, I only found three places.
Here's the two most relevant, from tarfile.py:
chk = 256
for c in buf[:148]: chk += ord(c)
for c in buf[156:]: chk += ord(c)
I wondered what it would look like using some of
the (all too many -- what happened to "should only be
one obvious way"!) variants:
# Using 'reduce'
chk = 256
chk = reduce(lambda x, y: x + ord(y), buf[:148], chk)
chk = reduce(lambda x, y: x + ord(y), buf[156:], chk)
# using the new 'sum' and a map
chk = 256
chk += sum(map(ord, buf[:148])
chk += sum(map(ord, buf[156:])
# using sum and list comprehensions
chk = 256
chk += sum([ord(c) for c in buf[:148])
chk += sum([ord(c) for c in buf[156:])
# using sum and the proposed generator expression
chk = 256
chk += sum( (ord(c) for c in buf[:148]) )
chk += sum( (ord(c) for c in buf[156:]) )
Personally, I think the existing code is the clearest
of the bunch, and the functional forms are too complicated.
In summary:
- I disagree with you that your text is the clearest way
to explain the 'reduce' function, since it is open to an
alternate interpretation and it doesn't help the people who
learn by understanding how things are implemented either
in code or in math.
- The use case you gave suggests that an alternate function,
which I named 'imax' (and 'imin'), is more useful, in part
because it does fewer operations
- In any case, for Python code the 'reduce' function is very
rarely used, so should not be something frequently pulled
from a Pythonista's toolbox and not taught in an intro. CS
course based on Python.
Andrew
da***@dalkescie ntific.com 
