loading...

Understanding Array reduce by building it from scratch

benlesh profile image Ben Lesh ・6 min read

Recently, I was involved in a thread on Twitter, where I mentioned that I also, at one time, found Array reduce challenging to wrap my head around. At first glance, it doesn't make any sense. The name, the signature of the thing, it's a bit alien in comparison to methods like map, filter, and forEach.

But what if I told you that each of the above methods are really just specializations of reduce?

Why is it called "reduce"? I'm not actually sure here. But how I remember what it does is that, generally, you're taking the array and you're "reducing it down" to something else. Now, this is a bit of a misnomer still, because you could use reduce to make a new, larger, array. But when I say "reduce", I mean more like "reduction" in cooking. You're taking your array, and you're making something else with it by running it through a process.


Starting with a basic loop

We already have ways to do this without any methods, of course. Considering the following:

const numbers = [1, 2, 3];
const plus1 = [];

for (let i = 0; i < numbers.length; i++) {
  const item = numbers[i];
  plus1.push(item + 1);
}

console.log(plus1); // [2, 3, 4]

Here, we have a source array, numbers, and we're looping over it, then we're updating a bit of existing state, the array plus1, by pushing values onto it derived from the items in our source array. It's efficient, and pretty simple, overall.

Now imagine we wanted to refactor this process into a few pieces so we could test it or reuse it in other ways. We could do the work inside of the loop in its own function:

function add1AndAppend(arr, item) {
  arr.push(item + 1);
}

const numbers = [1, 2, 3];
const plus1 = [];

for (let i = 0; i < numbers.length; i++) {
  add1AndAppend(plus1, numbers[i]);
}

console.log(plus1); // [2, 3, 4]

Now we have this function add1AndAppend we're calling on each loop. It's fine, but it's not great. For one thing, it's not a "pure" function, it's actually mutating the array we are passing to it. This means it could behave in undesirable ways, or be a pain to deal with later, as there's more to reason about. (There's been volumes written on the dangers of shared mutable state).

So we can refactor it to return a new array every time, making it "pure", in fact, I'll even rename it to add1AndConcat:

function add1AndConcat(arr, item) {
  return [...arr, item + 1];
}

const numbers = [1, 2, 3];
let plus1 = [];

for (let i = 0; i < numbers.length; i++) {
  plus1 = add1AndConcat(plus1, numbers[i]);
}

console.log(plus1); // [2, 3, 4]

And now we have this method, that we can easily test, that will take an array, and an item, and add 1 to the item, then create a new array that contains the items from the old array and the new item plus 1. We can reuse it, and we can test it:

expect(add1AndConcat([1, 2], 4)).toEqual([1, 2, 5]);

Creating a primitive reduce method

Wouldn't it be great if we had a method that could do these things for us (yes, yes, there's map, but that's not what we're learning about here yet).

function add1AndConcat(arr, item) {
  return [...arr, item + 1];
}

// This isn't the "real reduce" yet.
// Also, don't augment types like this in JavaScript. It's bad.
Array.prototype.reduce = function (callback) {
  let result = [];

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

  return result;
};

const numbers = [1, 2, 3];

const plus1 = numbers.reduce(add1AndConcat);

console.log(plus1); // [2, 3, 4]

Now, wouldn't it be nice if we could use this method for more things? Like what if we don't always want the result to be an array? What if we want an object? or a number? We need to be able to change what result is initialized to:

Array.prototype.reduce = function (callback, initialState) {
  let result = initialState;

  for (let i = 0; i < this.length; i++) {
    // We can pass the index to the callback too, because why not?
    result = callback(result, this[i], i);
  }

  return result;
}

// and we'd call it like so:
const plus1 = numbers.reduce(add1AndConcat, []);

So this is pretty useful! We can use it to do all sorts of things now. Maybe we can take an array of values and turn it into an object:

const keysAndValues = ['x', 20, 'y', 30, 'z': 3, 'name', 'Emma' ];

function toAnObject(obj, item, i) {
  if (i % 2 === 0) {
    // keys
    obj[item] = undefined;
  } else {
    // values
    obj[keysAndValues[i - 1]] = item;
  }

  return obj;
}

const obj = keysAndValues.reduce(toAnObject, {});
console.log(obj); // { x: 20, y: 30, z: 3, name: "Emma" }

BUT WAIT! That sucks! We can't really test that function because it's not "pure", as it's closing over keysAndValues as shared state. So what if we added one more argument to our callback, which is the source array:

Array.prototype.reduce = function (callback, initialState) {
  let result = initialState;

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

  return result;
}

function toAnObject(obj, item, i, source) {
  if (i % 2 === 0) {
    // keys
    obj[item] = undefined;
  } else {
    // values
    obj[source[i - 1]] = item;
  }

  return obj;
}

const obj = keysAndValues.reduce(toAnObject, {});
console.log(obj); // { x: 20, y: 30, z: 3, name: "Emma" }

And now we can test it:

const source = ['a', 1, 'b', 2];
expect(toAnObject({}, 'a', 0, source)).toEqual({ a: undefined });
expect(toAnObject({ a: undefined }, 1, 1, source)).toEqual({ a: 1 });
expect(toAnObject({ a: 1 }, 'b', 2, source)).toEqual({ a: 1, b: undefined, });
expect(toAnObject({ a: 1, b: undefined }, 2, 2, source)).toEqual({ a: 1, b: 2 });


No second argument

Probably the most confusing behavior of reduce

There's one quirk people don't often get, which is: What happens when you don't pass an initial state to reduce? The second argument is actually optional.

In the event that an initial state is NOT provided, the first value from the array will be "skipped" by the reducer function (the callback) and used as the initial state. These two things are equivalent:

[a, b, c].reduce(fn, INIT);

// is the same as

[INIT, a, b, c].reduce(fn);

This makes our fake reduce method above a lot more complicated:

Array.prototype.reduce = function (callback, initialState) {
  const hasInitialState = arguments.length > 1;

  let result = initialState;

  for (let i = 0; i < this.length; i++) {
    if (i === 0 && !hasInitialState) {
      result = this[i];
    } else {
      result = callback(result, this[i], i, this);
    }
  }

  return result;
}


DIY map and filter from reduce:

Well, we already sorta did a "map" above with the add1AndConcat, but let's just make a fake map right here:

map

Array.prototype.map = function (callback) {
  return this.reduce(
    (result, item, i, source) =>
      [...result, callback(item, i, source)],
    []
  );
}

Filter is more of the same, but this time we're asserting on a predicate before deciding to append to the result:

filter

Array.prototype.filter = function (callback) {
  return this.reduce(
    (result, item, i, source) =>
      callback(item, i, source) ? [...result, item] : result,
    []
  );
}

Reduce and reducer functions in the world at large

The callback to Array reduce is called a "reducer", and in recent years, its shape has been popularized by libraries like Redux, NgRx, and RxJS. It's a function signature for creating a pure function that is able to handle passing of some pre-existing state, as well as some value (such as an action, or other array item), then return a new state. In TypeScript that could be declared (very loosely, like so):

type ReducerFunction<T, S> = (currentState: S, item: T, index: number) => S; // returns new state

While Redux, RxJS and NgRx, are all doing things to state "asynchronously", as opposed to the synchronous behavior we see in Array reduce, the principles are exactly the same. An underlying state is initialized and maintained, and passed to the callback at each turn. In the cases of RxJS, Redux, and NgRx, the resulting state is something that requires subscription to observe.

In RxJS can can be expressed with scan:

import { of } from 'rxjs';
import { scan } from 'rxjs/operators';

function toSquares(result, number) {
  return [...result, number * number];
}

of(1, 2, 3).pipe(
  scan(toSquares, []);
).subscribe(x => console.log(x));

/**
 * [1]
 * [1, 4]
 * [1, 4, 9]
 */

But notice, we could reuse the same exact reducer with Array reduce:

[1, 2, 3].reduce(toSquares, []); // [1, 4, 9]

Special thanks to @EmmaBostian for inspiring me to write this article. It's knowledge that I've had for a long time and I take for granted. Hopefully others find this useful.

Posted on by:

benlesh profile

Ben Lesh

@benlesh

RxJS lead, former Angular team, former Netflix, React developer

Discussion

pic
Editor guide
 

I feel I have the potential to be an excellent developer but am not sure what steps to take next to become a Jedi, right now the force is weak with me. Can I get some references to good collaborative open source development I would appreciate this kind people.

 

There are two great things you can do to grow as a software developer, in my opinion: 1) find personal projects that genuinely interest you and that force you to learn new things, and 2) find open source repos that need help.

Doing the latter is admittedly easier than it sounds; what I'd recommend is heading over to GitHub's Explore section to find something relevant to your interests. Even if you don't find a project you can help with, you can at least get your hands dirty with setting up random projects from scratch on your own computer/dev environment.

 

Thanks for this simple article on reduce! I have a suggestion for changing the map method to a more performant version. Would love to see an article on rxjs's scan method!

The performance of this map is n2 because we are returning a new copied array inside the reducer method. Isn't this unnecessary immutability? Because we control the initial empty array state, we could mutate this array inside the reducer and still benefit from mutability for the caller of the map method.

Instead of this

Array.prototype.map = function (callback) {
  return this.reduce(
    (result, item, i, source) =>
      [...result, callback(item, i, source)],
    []
  );
}

We could do this -

Array.prototype.map = function (callback) {
  return this.reduce(
    (result, item, i, source) =>
      {
        result.push(callback(item, i, source))
        return result
      },
    []
  );
}
 

The beauty of reduce is, it's always pure by default.

I call this rendition "Everything is Reduce" 😁

github.com/vanillaes/absurdum

 

But when I say "reduce", I mean more like "reduction" in cooking.

I love that quote!