Understanding “reduce” (first in a series)

One of the notable things about MIT’s computer science curriculum, at least back when I was studying there, was that you didn’t learn any “practical” programming languages.  Our work was all done in either Scheme (a dialect of Lisp) or in CLU (an early object-oriented language).  I can’t say that I have too many memories, let alone fond ones, of CLU.  But I definitely drank the Kool-Aid about Lisp, and have long believed that it has always represented the pinnacle of programming languages.  Things that I learned long ago in Lisp are only now becoming standard in popular languages.

For example, functional programming has become increasingly popular in the last few years, for a variety of reasons including the shrinking effects of Moore’s Law — and the resulting need to have multiple, immutable copies of your data in the computer, distributed across multiple processors.  Lisp has long had many functional capabilities; it was Lisp that first introduced me to such functions as “map”, which I use multiple times each day.  However, my regular uses of “map” are rarely in Lisp; rather, they’re in Python and Ruby, the languages that I use most in my day-to-day work.

When I teach classes in Ruby and Python, I spend a fair amount of time talking about functional programming techniques.  It might sound funny to discuss functional programming in two languages that are so clearly object-oriented, but I actually find it quite natural.  Sure, I create classes and throw objects around.  But if I have an array of values, then it’s very fast and easy for me to process them with functional techniques.  Python’s list comprehensions have basically taken the place of the “map” and “filter” functions, so while those exist, they’re not as necessary any more.  But once you understand such functions as “map” and “filter”, you’re poised to do all sorts of amazing things.

Perhaps the most intriguing of the functions from this school is “reduce”.  I have found, consistently over time, that “reduce” is the function most likely to surprise and confuse newcomers to this type of programming.  That’s because it’s easy to confuse what “reduce” is doing, and to forget how flexible its output can be.

I’ve thus decided to write a series of blog posts about “reduce”, in both Python and Ruby.  I’ll start with the simple stuff, and then move ahead with increasingly complex tasks.  You won’t necessarily start to use “reduce” all of the time, but if you’re like me, you will find all sorts of interesting uses for it.  I tell people that I tend to use “reduce” about once every six months — but when I do use it, it really saves the day.

In Ruby, we can use the “reduce” method (also available as “inject”, to satisfy people from the Smalltalk world) on any enumerable object.  The invocation looks like this:

[1,2,3,4,5].reduce(0) {|a, b| a+b}

I’ll explain what this all means in a moment.  But the most important change that I can already make is to use better names for the block parameters:

[1,2,3,4,5].reduce(0) {|total, current| total+current}

Ruby goes through each element of the enumerable, invoking the block on each element. Described in this way, we might confuse “reduce” with “map”.  However, in “map”, the output is an array of the same length as the input.  By contrast, with “reduce”, the output of each iteration is remembered for the next time around.  That is, the value of “total” in each iteration is the block’s result from the last iteration.  

The initial value of “total”, in the first iteration, is the parameter value that we pass, which is 0 in this case.  If you don’t pass a parameter, then “total” is initialized with the first element of the enumerable, and the first iteration (i.e., the first application of the block) takes place on the second element.  This is fine in the above example, but depending on the output you want, failing to pass a parameter, or passing one of the wrong type, can make a big difference.

You can also think of “reduce” as a sort of “join”, but one that evaluates its inputs and operations.  So instead of getting the string “1+2+3+4+5”, you get the result of actually invoking 1+2, and then (1+2)+3, and then ((1+2)+3)+4, and then finally (((1+2)+3)+4)+5. This is why some Lisp versions call this “fold”, rather than “reduce”.  I still don’t quite get why Smalltalk people call it “inject”, and thus never use that term in Ruby (except when introducing the five rhyming functional methods — select, detect, collect, inject, and reject — because it’s so much fun to say). But the effect, once you internalize it, can be used in many interesting ways.

Python doesn’t have a “reduce” method on sequences, but does have a builtin “reduce” function that can be invoked on sequences.  (In Python 3, the “reduce” function was moved to the “functools” module — which is better than the fate Guido had originally planned for it.)  Python’s “reduce” is similar to the one in Ruby.  To sum numbers, we say:

>>> numbers = range(10)
>>> reduce(lambda total, current: total + current, numbers)
45

As you can see (I hope), the use of “lambda” to create an anonymous function is analogous to the use of a block in Ruby.  In Python’s “reduce” function, you first pass the function you wish to invoke on the sequence, and then the sequence itself.  If you wish to pass an initial value for “total”, you can do so with an optional third parameter:

>>> reduce(lambda total, current: total + current, numbers, 10)
55

The classic use of “reduce” is to sum integers, as we saw above.  But we can, of course, perform additional types of operations, and produce additional types of output.  And to be honest, that’s where “reduce” starts to get more intriguing.  Any operation that you want to perform on an enumerable, such as an array, set, or range, and apply cumulatively to its elements, makes for a good choice for “reduce”. By experimenting with the input enumerable, the initial value of “total” that we pass as a parameter, and the block, we can do many interesting things.

In coming posts, I’ll explore some more of these ideas, and give you a tour of “reduce” in both Ruby and Python that will hopefully open your eyes to some of them, and give you a sense of where “reduce” can help to improve your thinking, and your code.