Everything You Need to Know About Array#reduce

Cross-posted from my website's blog.

Array#reduce, or Array.prototype.reduce (referred to simply as reduce from here on), is my favorite function in the JavaScript standard library. Although it can take some time to get used to, it's 100% worth the effort. Once the power of reduce is fully grasped, it will enable you to redefine complex logic in a declarative, readable way.

This post is divided into two main sections: 1) an explanation of what reduce is and how it works, and 2) a demonstration of some interesting applications of reduce that you may not have previously considered. If you are a seasoned veteran with reduce, the explanation section will be review. Feel free to skip to the demonstration section.

What is reduce?

Simply put, reduce is a function that lets you reduce an array down to a single value. This value, which we'll call the reduced value, can be any type you want. You will often find yourself needing to reduce an array down to one of the many JavaScript primitive types, such as object, number, boolean, or even another array (we'll see some examples of this later!), depending on the circumstances. However, you are not limited to reducing to the primitive types. The reduced value can be any type you want, such as a Map, Set, or any custom type defined by your project.

In JavaScript, a reduce function is defined on the Array prototype (Array.prototype.reduce), which means you can call it on any array instance:

const myArray = [1, 2, 3];
const reducedValue = myArray.reduce(/* args */);

How does reduce work?

The array you call reduce on describes what you want to reduce, and the parameters passed into reduce describe how you want to build the reduced value from the array. The MDN documentation for reduce does a great job of detailing the inputs and outputs of reduce. Go take a look! I'll do a high-level overview here.

Parameters

1. The reducer function. Don't confuse this with a state management reducer function such as those used with Redux. Though the concepts are similar, they are not the same.
2. The initial value for the reduce loop.

The reducer function

When you call reduce on an array, reduce will iterate over the array one element at a time, invoking the reducer function once for each element. When reduce calls your reducer function, it passes the following four parameters in:

1. Accumulator
2. Current element
3. Current index
4. Source array

Don't worry too much about the last two parameters for now. In practice, I rarely find myself needing to use them.

The accumulator (sometimes called the collector) is the value that represents the results of invoking the reducer function on each element of the array up to, but not including, the current element. It's effectively the "reduced value so far". This is the essence of the reducer function:

The reducer function describes how to combine the accumulator (the reduced value so far) with the current element of the array to produce the accumulator for the next iteration.

The initial value (reduce's second parameter) acts as the accumulator for the first invocation of the reducer function, and the value returned from the final invocation of the reducer function is the final reduced value that is ultimately returned from the reduce call.

Case study: the sum function

We're all familiar with the sum function. Let's take a look at a simple implementation:

function sum(numbers) {
  let sumSoFar = 0;

  for (const number of numbers) {
    sumSoFar += number;
  }

  return sumSoFar;
}

What may not be obvious about the sum function is that it is actually just a special case of reduce. The sumSoFar variable acts as the accumulator:

function sum(numbers) {
  let accumulator = 0;

  for (const number of numbers) {
    accumulator += number;
  }

  return accumulator;
}

The body of the for loop is describing how to combine the current element (number) with the current accumulator to produce the next accumulator for the next iteration. This should sound familiar! With reduce, this is the job of the reducer function:

function sum(numbers) {
  let accumulator = 0;

  for (const number of numbers) {
    accumulator = reducer(accumulator, number);
  }

  return accumulator;
}

function reducer(accumulator, currentElement) {
  return accumulator + currentElement;
}

Notice how we've created a layer of abstraction by moving the logic for computing the next accumulator into a reducer function. At this point we're very close to having an actual reduce implementation. Let's finish it up by renaming a few things and allowing the reducer function and initial value to be passed in:

function reduce(array, reducer, initialValue) {
  let accumulator = initialValue;

  for (const currentElement of array) {
    accumulator = reducer(accumulator, currentElement);
  }

  return accumulator;
}

Supporting the last two parameters of the reducer function (the array index and the array itself) is trivial. To keep track of the current array index we can switch to a standard for loop instead of a for...of:

function reduce(array, reducer, initialValue) {
  let accumulator = initialValue;

  for (let i = 0; i < array.length; ++i) {
    accumulator = reducer(accumulator, array[i], i, array);
  }

  return accumulator;
}

Last but not least, with native reduce we don't need to pass in the array because we're calling reduce on the array. For illustrative purposes it looks something like the following, but keep in mind that we wouldn't run this code in production. There usually isn't a good reason to overwrite the behavior of native JavaScript functions:

Array.prototype.reduce = function(reducer, initialValue) {
  let accumulator = initialValue;

  for (let i = 0; i < this.length; ++i) {
    accumulator = reducer(accumulator, this[i], i, this);
  }

  return accumulator;
}

Notice that when the function is defined on Array.prototype, we can refer to the array itself as this.

What are some applications of reduce?

Let's take a look at some examples of reduce functions in the wild!

Some of the upcoming examples show functions defined on Array.prototype. Please note that it is not my intent to recommend that code like this be run in production. These examples are intended to demonstrate how some of the native Array.prototype methods could be implemented. In practice, we always want to use the existing native implementations rather than overwrite them with our own.

The sum function

We already saw how a simple sum function can be modified slightly to become the actual reduce function, but let's revisit sum to see how it is written using reduce:

function sum(numbers) {
  return numbers.reduce((accumulator, currentElement) => {
    return accumulator + currentElement;
  }, 0);
}

Notice the initial value, 0, and how the reducer function simply adds the current element to the accumulator to produce the next accumulator. By utilizing reduce we unlock an extremely declarative way to write this sum loop.

Although accumulator and currentElement are reasonable variable names to use in the context of a reduce loop, you'll find that in practice there are usually better names that are more appropriate to the context of the code being written. For example, in the case of the sum function, the names sumSoFar and number convey more circumstantial meaning and will probably more helpful for someone else (or even you!) reading the code during a code review or in the future:

function sum(numbers) {
  return numbers.reduce((sumSoFar, number) => {
    return sumSoFar + number;
  }, 0);
}

The map function

The map function is an extremely useful function that should be hanging from your toolbelt for quick and easy access. If it's not, go read about Array.prototype.map on MDN.

map calls a function (the "mapper" function, defined by you) on each element of an array, and returns a new array containing the results of each function call.

Here's an example of map in action:

function addOneToEach(numbers) {
  return numbers.map((number) => number + 1);
}

addOneToEach([1, 2, 3]) // [2, 3, 4]

What most probably haven't realized about map is that is actually just a special case of reduce! Unlike sum, where we reduce an array down to a number, with map we reduce an array down to another array. Because of this, we pass empty array as the initial value. Here's what it looks like:

Array.prototype.map = function(mapperFn) {
  return this.reduce((accumulator, currentElement) => {
    const mappedCurrentElement = mapperFn(currentElement);

    return [...accumulator, mappedCurrentElement];
  }, []);
}

Notice that the only thing the reducer function needs to do is run the current element through the passed-in mapper function and then add it to the end of the accumulator, which is initialized to an empty array.

The above implementation of map will have serious performance problems as the size of the input array grows. This is because the reducer function is creating a new array on each iteration and then copying the elements of the accumulator into it before finally appending the newly mapped current value. If you do the relevant math you will discover that the time complexity of this approach (assuming the time complexity of the mapper function is constant) is on the order of O(n²).

This is bad, so let's fix it! Instead of creating a new array on each iteration, there's no reason we can't keep using the same array through the entire reduction. On each iteration, we can push the mapped current element onto the array, and return it for the next iteration:

Array.prototype.map = function(mapper) {
  return this.reduce((accumulator, currentElement) => {
    const mappedCurrentElement = mapper(currentElement);

    accumulator.push(mappedCurrentElement);

    return accumulator;
  }, []);
}

This approach has two benefits:

• We've improved the time complexity to linear (or O(n)) time, and
• The array passed in as the initial value is the same array that is ultimately returned.

The filter function

This is another one to be familiar with! If you aren't, go check it out on MDN.

filter calls a function (the "filter" function, defined by you) on each element of an array, and returns a new array containing all of the elements of the original array for which the filter function returned a truthy value.

Here's an example of 'filter' in action:

function removeUndefined(array) {
  return array.filter((x) => x !== undefined);
}

removeUndefined([1, true, undefined, 'hi']); // [1, true, 'hi']

What may not be completely apparent is that filter is also just a special case of reduce! Its implementation using a reduce loop is very similar to that of map. The only difference is that map's reducer function unconditionally appends the mapped element to the accumulator, whereas filter's reducer function conditionally appends the original element to the accumulator depending on the result of calling the filter function with that element. Here's what it looks like:

Array.prototype.filter = function(filterFn) {
  return this.reduce((accumulator, currentElement) => {
    if (filterFn(currentElement)) {
      accumulator.push(currentElement);
    }
    return accumulator;
  }, []);
}

Cool!

The some function

Not to be confused with the sum function that we've already spent some time talking about. The some function tends to be a little less well-known than map and filter, but it has use cases and definitely deserves a minor-supporting role in your toolbelt. Go take a look if you're new to some.

some calls a function (the "test" function, defined by you) on each element of an array, and returns a boolean indicating whether or not the test function returned a truthy value for any element in the array. It "short circuits" as much computation as possible by terminating the array iteration as soon as an element is encountered for which the test function returns a truthy value.

Here's an example of some in action:

function gotMilk(array) {
 return array.some((x) => x === 'milk');
}

gotMilk(['juice', 'water']); // false
gotMilk(['juice', 'milk', 'water']); // true

You've probably already guessed where this is going... Yes—some is actually just a special case of reduce. Unlike sum (where we reduce down to a number) and map and filter (where we reduce down to an array), with some we reduce down to a boolean. The boolean accumulator indicates whether or not any value of the array so far has returned truthy from the test function. Because of this, we initialize the accumulator to false, and once it gets flipped to true we stop calling the test function on the rest of the array:

Array.prototype.some = function(testFn) {
 return this.reduce((accumulator, currentElement) => {
   if (accumulator) { return accumulator; }
   return testFn(currentElement);
 }, false);
}

The reduce implementation of some is slightly less performant than the native implementation. The native implementation stops iterating as soon as a truthy value is encountered, whereas the reduce implementation only stops calling the test function but does not stop iterating. We could fix this by throwing an exception from the reducer function when we reach a truthy value, catch the exception outside, and return true. However, this defeats the purpose of using reduce in the first place.

The reason for showing an implementation of some that uses reduce is to illustrate that the idea of the some function is a special case of the reduce function, even though a performant implementation of some cannot be easily written using reduce.

And also these!

Similar to some, the following Array.prototype methods are all special cases of reduce and can be implemented using simple reducer functions:

• every
• find
• findIndex
• indexOf
• flat

As we saw with some, a few of these functions are able to terminate the array iteration early and therefore cannot be performantly implemented using reduce. In spite of this, it is valuable to observe that they all are specific situations in which we want to reduce an array down to a single value.

So what?

The reduce function represents a simple idea: the reduction of an array down to a single value. Not surprisingly, it also boasts a simple implementation. So simple, in fact, that we can achieve it by making a few minor changes to a simple sum function!

But we shouldn't be fooled by reduce's simplicity in these regards. The power and applicability of reduce is evident in the sheer number of functions on the Array prototype (such as map, filter, and some) that are just special cases of reduce and can be implemented with simple reduce loops. This is not to suggest that we should use reduce instead of these more specific functions. Using the special cases of reduce (instead of reduce itself) improves the readability of your code! Rather, I'm pointing this out to showcase the power of reduce.

Power and beauty exist in simplicity. They do not require complexity. On the contrary, complexity should be avoided as much as possible! Think of it this way: a simple solution to a problem is going to be much easier to implement. It will be harder to accidentally write bugs into. It will be easier for another programmer to take over and build upon or change. It will be easier to test. The list goes on!

In the words of the great Edsger W. Dijkstra:

Simplicity is a great virtue but it requires hard work to achieve it and education to appreciate it. And to make matters worse: complexity sells better.

And:

Simplicity is prerequisite for reliability.

Simple solutions are better than complex ones is almost every way imaginable. What's difficult is coming up with simple solutions. This is a skill that you will spend your entire career developing and never perfect.

That's all I've got for now! Hopefully you've been inspired not only to look for opportunities to reduce in your own code, but also to pursue simpler solutions when you have the bandwidth to. It will pay off in the long run!

Happy coding!

Like this post?

Follow me on Twitter where I (re)tweet about frontend things: @worsnupd

Comments

[Evan Plaice]

Great article. It's good to finally see somebody write about reduce in depth.

If you want to see this idea explores further check out

github.com/vanillajs2/absurdum

It's a WIP but it's a lot like lodash except every functional operator is implemented using only reduce.

[Daniel Worsnup]

Thanks!! And thanks for the link. I might update the article to link to this!

[Evan Plaice]

Cool. I always appreciate a mention.

You mentioned a bunch of useful operators that aren't in the library. I'll be sure to add those to the roadmap.

[Peter Ellis]

Nice summary, thanks for writing it up. "Reduce" is an important concept in many contexts, so if you understand it once, the others will be a lot easier.

I think there's an error in one of the code snippets, where you use this line:

accumulator = reducer(accumulator, this[i], i, array);

I think instead it should be:

accumulator = reducer(accumulator, this[i], i, this);

Because at that point there is no array variable.

[Daniel Worsnup]

Hi Peter! Thanks for pointing out my mistake! I'll fix it tonight. And yes I agree completely. Reduce is a very important function!

[Jesse Phillips]

Nice explanation. It is unfortunate that the language must reduce into a new array. D uses the concept called a range, filter and map do not reduce to an array. Instead they are a range the applies on another range. This means map and filter can be applied with (multiple times) and it is still O(n).

[Daniel Worsnup]

Just read about it. Ranges look really useful!

[Jesse Phillips]

It is funny because Ranges a close to c# LINQ or Java stream. D got to really build its algorithms around it (well technically many types of ranges).

Though coding with lazy evaluation can have its surprises when you're not always aware of the implications.

For example several grouping functions, like chunkBy, require the range to be sorted by the grouping. Sorting is eager, but grouping doesn't need to be. And you can group an unsorted range which could have value... Maybe.

[Anton Ödman]

Great post - got a much better understanding of the reduce function now! 👏

[Daniel Worsnup]

I'm so glad the post helped!

[Homam]

Nice post. I also wrote about defining array operations using reduce from a FP perspective: dev.to/homam/reduce-213

[Daniel Worsnup]

Cool, thanks for the link! I'll check it out!