Write A Reduce Function From Scratch


This post is by Hashrocket from Hashrocket


Click here to view on the original site: Original Post




JavaScript's Array object has a built-in reduce method. This is a handy,
yet underutilized method. Let's take a closer look at what reduce does and
see if we can implement it from scratch.

Reduce?

Here is what
MDN
has to say about reduce:

The reduce() method executes a reducer function (that you provide) on each
member of the array resulting in a single output value.

So, we can take an array of things and turn it into something else using a
function that we get to define.

const sum = list => list.reduce((total, val) => total + val, 0);

sum([1,2,3,4]) // => 10

The reduce method can seem pretty limiting at first when we read that it
produces "a single output value." That makes it sound like all it is good
for things like a sum function. The reduce method can also produce
an array as its single output value. Objects too!

const countWords = wordList => {
  return wordList.reduce((acc, word) => {
    acc[word] = (acc[word] || 0) + 1;
    return acc;
  }, {});
};

countWords(["hello", "world", "hello", "dogs", "hello", "cats"]);
// => {hello: 3, world: 1, dogs: 1, cats: 1}

This method can do just about anything. It's very versatile. I'll say more
about that at the end.

Implement Our Own

Let's push our understanding of reduce a bit further by implementing our
own.

What we ought to have noticed in the examples above is that there are three
standard parts to a reduce. First, there is the list to be reduced. Then
there is always some initial value. For sum it was 0 and for
countWords it was {}. Third, and perhaps most importantly, is our
reducer function.

We can stub out a naive version with just this knowledge:

const myReduce = (list, initialValue, reducer) => {
  return initialValue;
}

This naive implementation will even work in cases where list is empty.

myReduce([], 0, (total, val) => total + val); // => 0

That there is an important observation. Once we have an empty list, we
should return whatever our initialValue is. This is what is known as our
base case or terminating case. The full implementation will involve
recursive calls of itself, so it is important to understand when and how we
terminate the process.

const myReduce = (list, initialValue, reducer) => {
  if(list.length === 0) {
    return initialValue;
  }
}

We are still missing the meat of the function. We need to decide what
happens when there are items left in the list. This is where our reducer
function comes into the picture.

The Reducer

The general shape of the reducer function is important. It takes two
values as arguments: the accumulator, what everything is being reduced
into, and the current value we are reducing. It then performs some reduction
logic and returns a new version of the accumulator.

Let's look back at our reducer function for sum:

(total, val) => total + val

The accumulator is the total of our summing so far and the current value is
val. We had those two values together, returning them as the new version
of the accumulator.

The reducer function for countWords is a bit more complicated:

(acc, word) => {
  acc[word] = (acc[word] || 0) + 1;
  return acc;
}

The accumulator is some object full of words and respective counts. We
have to first update the accumulator with the next word accounting for
whether or not it is the first time we've seen this word. Then the updated
accumulator is returned.

Now Reduce

With that in mind, let's handle the case where we get to use the given
reducer function.

const myReduce = (list, initialValue, reducer) => {
  if(list.length === 0) {
    return initialValue;
  } else {
    const [first, ...rest] = list;
    const updatedAcc = reducer(initialValue, first);
    return myReduce(rest, updatedAcc, reducer);
  }
}

We need to access the next value to be reduced, hence the list
destructuring. We then apply the reducer function with the initialValue
and that next list value. Because this is a recursive function, we can think
of the accumulator value being the initialValue of that given step of
the reduce.

With our new accumulator value (updatedAcc) in hand, we can continue to
reduce with a recursive call on the rest of the list.

And that's it. In just a couple lines of code we've implemented reduce
with JavaScript (ES6) primitives.

Let's update countWords to use our version of reduce:

const countWords = wordList => {
  return myReduce(wordList, {}, (acc, word) => {
    acc[word] = (acc[word] || 0) + 1;
    return acc;
  });
};

Conclusion

The reduce method is a bit unapproachable. Yet it is a powerful and
versatile method that can take the place of methods like map, find, and
filter. We broke reduce down into its constituent parts and then
implemented our own from scratch. Go forth and reduce!


Cover photo: unsplash-logoReuben Teo

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.