Enumerating Enumerable: A Cute Trick for Explaining inject / reduce / fold

The next method I’m going to cover in Enumerating Enumerable — the series of articles in which I try to do a better job of documenting Ruby’s Enumerable module than Ruby-Doc.org does — is inject, a.k.a. reduce. Not only is it one of the trickiest methods to explain, it’s also one of the cornerstones of functional programming. I thought that I’d take a little time to explain what the function does.

inject

The term inject comes from Smalltalk and isn’t terribly descriptive. I remember reading the documentation for it and being all confused until I saw some examples. I then realized that I’d seen this function before, but under two different names.

reduce

Burning Man 1999: gratuitous nudity and even more gratuitous accordion!

The second name by which I encountered this function is reduce, and it was at Burning Man 1999. I was to start a new job the week after Burning Man, and I had to learn at least some basic Python by then. So along with my camping gear, accordion and a kilo of candy for barter, I also brought my laptop (a 233Mhz Toshiba Sattelite with a whopping 96MB of RAM) and O’Reilly’s Learning Python and noodled during the downtime (early morning and afternoon) on Python 1.6. When I got to covering the reduce function, I was confused until I saw some examples, after which I realized that I’d seen that function before, but under a different name.

(You may have also heard of reduce through Google’s much-vaunted MapReduce programming model.)

fold

The first name by which I encountered this function is fold, or more specifically, “fold left” or “foldl”, and it was at the “Programming Paradigms” course I took at Crazy Go Nuts University. “Programming Paradigms” was a second-year course and had the reputation of being the most difficult course in the computer science curriculum. The intended purpose of this course was to provide students with an introduction to functional programming (these days, they use Haskell and Prolog, back then, it was Miranda). Its actual effect was to make most of the students swear off functional programming for the rest of their lives.

In spite of the trauma from this course, I ended up remembering a lot from it that I was able to apply, first to Python and now to Ruby. One of these things is a cute little trick for cememnting in your mind what fold does.

What Ruby-doc.org Says

Before I cover that cute little trick, let’s take a look at what Ruby-doc.org’s documentation has to say about Enumerable‘s inject method.

One thing you’ll find at Ruby-doc.org is that as of Ruby 1.8.7 and later, inject gained a synonym: the more familiar term reduce.

As for the description of the inject/reduce method, I don’t find it terribly helpful:

Combines all elements of enum by applying a binary operation, specified by a block or a symbol that names a method or operator.

If you specify a block, then for each element in enum<i> the block is passed an accumulator value (<i>memo) and the element. If you specify a symbol instead, then each element in the collection will be passed to the named method of memo. In either case, the result becomes the new value for memo. At the end of the iteration, the final value of memo is the return value fo the method.

If you do not explicitly specify an initial value for memo, then uses the first element of collection is used as the initial value of memo.

(Yes, those stray <i> tags are part of the text of the description for inject. Hopefully they’ll fix that soon.)

This confusing text becomes a little clearer with some examples. The most typical example of inject/reduce/fold in action is the classic “compute the sum of the numbers in this range or array” problem. There are a number of approaches you can take in Ruby, all of which use inject/reduce:

(1..8).reduce(:+)
=> 36

(1..8).reduce {|sum, number| sum += number}
=> 36

(1..8).reduce(0) {|sum, number| sum += number}
=> 36

The reduce method takes some kind of operation and applies it across the enumerable to yield a single result. In this case, the operation is addition.

Explaining how that operation is applied is a little trickier, but I do just that in the next section.

Demonstrating inject / reduce / fold With a Piece of Paper and Literal Folding

To explain what’s happening in the code above, I’m going to do use a piece of paper. I’ve folded it into 8 even sections and then numbered each section, as shown in the photo below:

Think of the paper as the range (1..8). We’re now going to compute the sum of the numbers in this range, step by step, using a literal fold — that is, by folding the paper. I’m going to start folding from the left side of the paper, and when I do, I’m going to add the numbers that I’m folding into each other.

In the first fold, I’m folding the number 1 onto the number 2. Adding these two numbers yields 3, which I write on the back of the fold:

For the second fold, I fold the first number 3 onto the second number 3. The sum of these two numbers is 6, and I write that on the back of the resulting fold:

I fold again: this time, it’s the number 6 onto the number 4, the sum of which is 10. I write that number down on the resulting fold:

Next, I fold 10 onto 5, yielding the number 15:

I then fold 15 onto 6, which gives me 21:

Next comes 21 folded onto 7, which makes for a sum of 28:

And finally, 28 folded onto 8, which gives us a final total of 36.

And there you have it: a paper-based explanation of inject/reduce/fold, as well as why I often refer to the operation as “folding”.