Home

Reduce in JavaScript

04 March 2019

Russian translation: Уменьшение в JavaScript

When interviewing candidates, I used to ask them about several native methods of Array in JavaScript they had used and let them implement one of the methods on paper, such as some or map. If someone knows that functions can be passed around, this should not be a hard task.

The reduce function was most rarely mentioned.

The discussion

Last week Sophie Alpert tweeted about her rule for the reduce function. There was then a hot discussion, as the last two rules in the list were controversial among many people.

I myself use this function a lot. Not only for summing and multiplying numbers, but also for composing a new array or object. Sophie's rule made me think about this function again.

Reduce vs Fold

Reduce is a higher-order function which is usually called fold in functional programming languages. For me, fold is definitely a better name compared to reduce, since this's how it behaves like folding a fan in my head.

It also has directions, reduce traverses a list from left to right, reduceRight does from the other direction. You've probably seen foldl and foldr somewhere else, they're the same thing but much readable.

In JavaScript, if no initial value is supplied to the reduce function, the first element in the given array will be used. 

[1, 2, 3].reduce((a, b) => a + b, 0);

// The 1st element is used as initial value
// when the 2nd argument is missing.
[1, 2, 3].reduce((a, b) => a + b);

That's why I prefer foldl1 or foldr1 in other languages like Haskell, which explicitly uses the first or last element as initial value. 

foldl (+) 0 [1, 2, 3]

-- More intuitive
foldl1 (+) [1, 2, 3]

Two tasks

There are two simple tasks by given the following data, and solutions with normal loops: 

const scoreArray = [
  { name: 'Jim', score: 99 },
  { name: 'Han', score: 55 },
  { name: 'Tom', score: 87 },
  { name: 'Ana', score: 50 }
];

a) Get the total score of all items. 

function getScoreSum(array) {
  let ret = 0;
  array.forEach(item => {
    ret += item.score;
  });
  return ret;
}

b) Get the item with the highest score.

function getHighest(array) {
  let ret = {};
  array.forEach(item => {
    if (!ret.score || (ret.score < item.score)) {
      ret = item;
    }
  });
  return ret;
}

Seeing patterns

The above two functions have something in common:

  1. An initial value.
  2. A rule on how to update the initial value with each item in the list.
  3. Returns the final updated value.

We can define a function to abstract the repeated pattern. This is actually a simple version of Array.prototype.reduce. 

function reduce(array, rule, initial) {
  // initialization
  let result = initial;
  // traverse through the list and update the result
  // according to the custom rule
  array.forEach(item => {
    result = rule(result, item);
  });
  // return the final result
  return result;
}

Now rewrite the solutions to see how they will look like with reduce.

function getScoreSum(array) {
  return reduce(array, (ret, item) =>
    ret + item.score, 0
  );
}
function getHighest(array) {
  return reduce(array, (ret, item) =>
    ret.score > item.score ? ret : item, {}
  );
}

Once you identify this pattern, the code will be more understandable. The benefit of the abstraction is that the rule can be separated and possibly be reusable. 

function maxByScore(a, b) {
  return a.score > b.score ? a : b;
}
function getHighest(array) {
  return reduce(array, maxByScore, {});
}

The difference

The above getScoreSum() and getHighest() also have a different place.

  1. getScoreSum() returns a number.
  2. getHighest() returns an object, the type is same with items in the list.

Normally it's called asymmetrical in its types when the type of the returned value is different from the type of items in the list. Otherwise, it is symmetrical.

The first two rules in Sophie's tweet basically referred to symmetrical functions. 

.reduce((a, b) => a + b, 0);
.reduce((a, b) => a * b, 1);

Sometimes it's convenient to make the first element as the initial value when it's symmetrical. Also, we could reduce one iteration in the loop. So here are little modifications to the reduce function we just defined. 

function reduce(array, rule, initial) {
  let hasInitial = arguments.length > 2;

  // make the first element as initial value
  // when the initial argument is missing
  let result = hasInitial ? initial : array[0];
  let start = hasInitial ? 0 : 1;

  for (let i = start; i < array.length; ++i) {
    result = rule(result, array[i]);
  }
  // return the final result
  return result;
}

Much simpler now: 

function getHighest(array) {
  return reduce(array, (a, b) => a.score > b.score ? a : b);
}

Building up a list

A good use case of building lists with reduce is the implementation of the flat or flatMap function. 

const nestedArray = [
  1, 2, 3, [4, 5], 6
];

With the normal loop:

function flat(array) {
  let ret = [];
  array.forEach(n => {
    ret = ret.concat(n);
  });
  return ret;
}

Again, we see the pattern exposes. So let's try to do it with reduce. 

function flat(array) {
  return array.reduce((ret, n) => ret.concat(n), []);
}

As you can see it's not that bad. We can go further to support flattening on deep nested array: 

const nestedArray = [
  1, 2, 3, [4, 5],
  [[6, 7], 8], 9, 10
];

function flat(array) {
  return array.reduce((ret, n) =>
    ret.concat(Array.isArray(n) ? flat(n) : n), []
  );
}

Other examples

Some other functions can also be implemented with reduce easily. We can do this as a practice regardless of some performance concerns. 

function map(L, fn) {
  return L.reduce((acc, n, i) => [...acc, fn(n, i, L)], []);
}

function reverse(L) {
  return L.reduce((acc, n) => [n, ...acc], []);
}

function join(L, sep='') {
  return L.reduce((a, b) => a + sep + b);
}

function length(L) {
  return L.reduce(acc => acc + 1, 0);
}

Thoughts

Abstractions are ways of thinking.

If the performance is not crucial I still prefer to use reduce function whenever appropriate. Because it allows me to focus on the most important part and write less code.