Python's simplicity philosophy

[Andrew Dalke]

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
2417851639229258349412352L
>>> (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(seq[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_matching_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.keys(),
                           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
                    dalke at dalkescientific.com