What is Reduce?

May 08, 2018 0 Comments

Ah, "reduce." The Swiss Army knife of iterative functions. Known as "fold" to func-y monks1. Is there anything it can't do to a list? No. Are there things it shouldn't be used for? Yes. But, a great way to develop a firm understanding of the strengths and limitations of something is to use it as your only tool for every task. So let's do that. I'm going to use ES6 for this article, but I also make reference to the Object.entries and Object.values ES2017 proposals, which you will need a tool like Babel in order to use.

What is Reduce?

To generalize reduce to its most basic form, we can define its type signature. Here is a simplified version:

(reducer: Function, initialValue: Any, list: Array): Any

Reduce takes a function to be invoked on each item in a list, an initial value, and a list, and returns a value. To generalize further, it takes a list and returns any value. The return value could be a string, boolean, object, another list, null, a number, anything. This may sound very generic, and that's because it is.

Reduce "accumulates" its final return value by invoking the reducer function you pass to it on every iteration and passing its return value to the next iteration. This return value is commonly called the "accumulator" or sometimes the "reduction." On the first iteration, the accumulator starts out equal to the initial value we pass to reduce. The reducer gets passed the accumulator and the current element in the list. (Note, the reducer function might sometimes get called the "iteratee," an academic term for a function that gets called on each iteration of a loop.)

Here's a contrived example of what we've discussed thus far:

https://gist.github.com/8a3eebd74972a2e1f345772a4ff67caf

Implementing Reduce

So how would we implement this in ES6? Well, we need a function that takes three arguments: an iteratee, an initial value for the accumulator, and an array to be operated on. We will write this as a curried function and place the most specific argument (the array) last. (From this point on, I encourage you to crack open your browser's JavaScript console and hack along as we go.)

https://gist.github.com/3d7e9f6129db17e9bc6e3c08bd17c430

(Note: the "accumulator" argument is where we'll pass our initial accumulator value when using this function. The naming is a little different from what we looked at above, but it will make sense as we move on.)

We're going to implement this in a recursive way, and the first question when writing a recursive function is always: what will its terminal condition be? In this case, we want to return the final accumulator value when we have no more items left in our array.

https://gist.github.com/14eec6b79e73ede4def6990d8b5b7046

If we have elements left in the array, we want to recursively call our function by passing the same arguments, but we will split up the array by passing the first element in it to the reducer (along with the accumulator) and the remaining elements as the last argument to reduce.

https://gist.github.com/33e31467490084a8f88a9f2433b239b5

On each recursion, we pass 1) the same reducer function again 2) a new, updated accumulator value calculated by invoking the reducer with the current accumulator value and the first item in the list 3) the rest of the list. If there are no more items in the list, we return the accumulator (the "reduction").

The sentence in bold in the paragraph above is important because that's where the work gets done.

Now let's see if this works. Since we made our reduce a curried function, we can pass every argument except for the actual array to be operated on and get a ready-made function that we can use on any array. Say we want to make a function that sums all the items in an array of numbers. We can pass an iteratee that simply returns the sum of the accumulator and the current element in the array, and a starting value of 0.

https://gist.github.com/9cd15f3cc6ac7ead9a04e1dd73c8600d

Yay! It works.

Trivial Examples Are Fun

Here are some more basic things implemented via reduce:

https://gist.github.com/ffce6559501f9f6ba0d6aec6c5605b0e

You may sometimes encounter code similar to the above except much more terse:

https://gist.github.com/af6ccebdf0da358a47e618e3f53ddcd1

Reduce is a very well known tool, so developers may not go out of their way to make the code as descriptive as possible when it's simple enough to speak for itself like our all implementation above. Sometimes it's OK for code to just look like code.

Every Iterative Function Is a Special Case of Reduce

We can even implement map and filter with reduce.

https://gist.github.com/dfca22636b08a72e8426fd7e1c795056

Obviously, this is silly because...

Sometimes There Are More Semantic Options

The last example illustrates how incredibly flexible reduce is. However, map is made to map things. Filter is there to filter things. They are there for those specific jobs. If you only need to map an array, use map. That said, if you're deriving a new list by calling map and then filter on a list, and you have a ridiculous number of elements in the list, you could cut your number of iterations in half by doing both the map and the filter within one reduce. And in some cases, this might even be more readable.

Along the same lines, if the native array methods like every, includes, some or all do what you need, then use those because they're less verbose and more descriptive and direct. Libraries like immutable.js and lodash have their own built-in versions of these common utilities, though, of course, the names may differ slightly ("all" instead of "every," for example).

Oh No! How Do I Reduce An Object?

It's easy. Reduce operates on arrays, so call Object.keys if you need to reduce the object's keys, Object.values if you need to reduce the values, or Object.entries if you need to look at both on each iteration.

https://gist.github.com/20d8b2b0ca0b691c9ffa3940e328e2ad

Implementing MapFunction with Reduce

Here's a bit of a novelty for supernerds who want to dig further. Say you have a need to create a function that performs map with some given iteratee logic. We can use our curried reduce to implement this "map function" function. What we want is to be able to pass a function as the argument to mapFunction and then get our custom mapper back, ready to operate on any and every array in sight.

https://gist.github.com/fcae1152dd1bfda9e59c97d1fbd0a6e7

Hey! That was easy. Could you pass the functions, please? Boy, this curry is delicious.

That was a good demonstration of the versatility of reduce, but there's a far easier way to do it via the map function and, once again, currying. All we need to do is take a function as an argument and return a function that takes an array and maps the array with the given function:

https://gist.github.com/cb9750e4a8f580d468f4a2473f089051

If you've made it this far and understand the code, then congrats. You have grokked some of the fundamental building blocks of functional programming. If you like this approach, I highly recommend checking out Learn You a Haskell for Great Good.

Now That You've Suffered

JavaScript is nice to us and has reduce as a native array method, as well as a slew of other handy methods, as of ECMAScript 5.1, which means we can simply call reduce on the array itself instead of passing the array as an argument to a separate reduce function. We can also optionally omit the initial value, which will cause the first and second elements to be passed as arguments to the reducer on the first iteration (the tables here provide an excellent explanation).

https://gist.github.com/1d10f11c32a236e4d3c2350dd455731c

And here's a handy little example straight from the MDN docs:

https://gist.github.com/d95bce28c3a853f95f9d62fecfa43370

Reducing Empty Arrays

One important thing to know about Array.prototype.reduce is that if you do not provide an initial value when calling reduce on an empty array, a TypeError exception will be thrown.

Final Note on the Dreaded forEach (TL;DR - It's Gross.)

Sometimes we think we need to use an impure function like forEach, but we really just need to make a data structure that is like one we have defined but transformed a bit. We can make our code more safe and declarative by using reduce instead. For example, you can use a fleshed out object as the initial value, like this:

const newThing = things.reduce(reducer, { some: 'interesting', stuff: [] })

Or, if you do indeed need to use an existing reference to an object as your initial value and you want to avoid the side-effects of modifying that object within your reduce and just getting the same object reference back, use a deep-cloning utility like lodash.cloneDeep.

const newThing = things.reduce(reducer, cloneDeep(importantObject))

The above techniques can also be applied with arrays, of course. Instead of putting a new, empty object in a variable and then forEach-ing an array to mutate that object, just reduce the array into a new object, passing an empty object literal as the initial value.

Only use forEach if you truly need to cause an external side-effect on each iteration.

Adios

That's it! Thanks for reading :-)

######PS: I had been meaning to write this article since forever. A few days before finishing it, I discovered this academic paper by Graham Hutton that discusses the same topic but at a higher level of ascended, godlike wizardry. If you have the fortitude to slog through it, it's quite impressive: "A Tutorial on the Universality and Expressiveness of Fold"

######PPS: Lovingly dedicated to the eternal memory of Pankaj's Purple Pancake Packaging Providers.

2: F# and Scala make slight distinctions between reduce and fold, but most languages don't, so I'll use the terms interchangeably here.

https://gist.github.com/granmoe/19587cf1c6261672cd4d46412a725db6#file-blog-md


Tag cloud