Reduce

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:

const reducer = (accum, current) => accum + current  
const initialValue = 0  
const list = [1, 2, 3]

reduce(reducer, initialValue, list) // 6  

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.)

const reduce = (reducer, accumulator) => arr => 'todo'  

(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.

const reduce = (reducer, accumulator) => arr =>  
  arr.length
    ? 'todo'
    : accumulator

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.

const reduce = (reducer, accumulator) => arr =>  
  arr.length
    ? reduce(reducer, reducer(accumulator, arr[0]))(arr.slice(1))
    : accumulator

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.

const sum = reduce((accum, current) => accum + current, 0)  
sum([1, 2, 3]) // 6  

Yay! It works.

Trivial Examples Are Fun

Here are some more basic things implemented via reduce:

const product = reduce((accum, current) => accum * current, 1)

const all = reduce((accum, current) => accum && current, true)

const any = reduce((accum, current) => accum || current, false)

const length = reduce(accum => accum + 1, 0)

const reverse = reduce((accum, current) => [current].concat(accum),  
 [])

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

const all = reduce((a, b) => a && b, true)  

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.

[1, 2, 3].map(x => x * 2)

// is equivalent to

reduce((accum, current) => accum.concat([current * 2]), [])([1, 2, 3])



[1, 2, 3].filter(x => x > 2)

// is equivalent to

reduce((accum, current) => current > 2 ? accum.concat([current]) : accum, [])([1, 2, 3])

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.

const addPrefix = prefix => reduce((result, [key, val]) => {  
  result[prefix + key] = val
  return result
}, {})

const myObj = {  
  foo: 1,
  bar: 2
}

addPrefix('yo_')(Object.entries(myObj))  
// returns { yo_foo: 1, yo_bar: 2 }

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.

const mapFunction = func => reduce((accum, current) => accum.concat([func(current)]), [])

const double = mapFunction(x => x * 2)  
double([1,2,3])  
// returns [2, 4, 6]

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:

const mapFunction = func => arr => arr.map(func)

const double = mapFunction(x => x * 2)  
double([1, 2, 3])  
// returns [2, 4, 6]

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).

let arr = [10, 2, 4]  
// product
arr.reduce((a, b) => a * b) // 80

arr = [false, true, true]  
// all
arr.reduce((a, b) => a && b) // false

// any
arr.reduce((a, b) => a || b) // true

// length (obviously, just use the length property instead in real code)
arr.reduce((a) => a + 1, 0) // 3

// reverse
arr.reduce((a, b) => [b].concat(a), []) // [true, true, false]

// add a prefix to all the first child key names of an object
const addPrefix = (prefix, obj) =>  
  Object.entries(obj).reduce((result, [key, val]) => {
    result[prefix + key] = val
    return result
  }, {})

// addPrefix usage
const myObj = { a: 1, b: 2 }  
addPrefix('hidy-ho-errybody__', myObj)  
// returns { hidy-ho-errybody__a: 1, hidy-ho-errybody__b: 2 }

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

var list1 = [[0, 1], [2, 3], [4, 5]];  
var list2 = [0, [1, [2, [3, [4, [5]]]]]];

const flatten = arr => arr.reduce(  
  (acc, val) => acc.concat(
    Array.isArray(val) ? flatten(val) : val
  ),
  []
);
flatten(list1); // returns [0, 1, 2, 3, 4, 5]  
flatten(list2); // returns [0, 1, 2, 3, 4, 5]  

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.

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

comments powered by Disqus