Reduce reigns supreme

Transducers are all the rage lately. They allow you to efficiently compose operations on a list without creating individual intermediate array (good, no garbage collection pauses). If you look at the examples you might notice a weird thing: all array operations are implemented using Array.prototype.reduce rather than individual operations (like map, some, filter). Why is that?

Typically we use reduce to produce single value from a given list. For example to compute the sum of numbers we can write

var numbers = [3, 1, 7];
var sum = numbers.reduce(function (total, x) {
  return total + x;
}, 0);
console.log('sum of', numbers, '=', sum);
// sum of [ 3, 1, 7 ] = 11

The key to understanding why reduce is so popular is to notice that the output value could be anything: an integer (like a sum), or a boolean (like a flag), or even another array (for example filtered values). In other words, every other list operation can be quickly implemented using reduce!

reducing forEach

Let us start with a simple print each number feature. It can be implemented using Array.prototype.forEach or reduce

// need to print each number
numbers.forEach(function (x) {
  console.log(x);
});
// 3 1 7
// OR
numbers.reduce(function (whatever, x) {
  console.log(x);
}, 0);
// 3 1 7

We can completely ignore the first argument in the reduce callback, because we are only interested in the value of each item x.

refactor reduce to replace forEach

We can refactor the callback to forEach and reduce any such transformation using ignore-argument utility.

function print(x) {
  console.log(x);
}
numbers.forEach(print);
// 3 1 7
var ignore = require('ignore-argument');
numbers.reduce(ignore(print, true), 0);
// 3 1 7

reducing map

The second method we can implement using reduce is Array.prototype.map that creats new list by passing each item through a callback. Let us double each number.

var doubled = numbers.map(function (x) {
  return x * 2;
});
console.log('doubled numbers', doubled);
// doubled numbers [ 6, 2, 14 ]

The same feature can be quickly implemented using reduce if we start from an empty array and push each doubled number to it.

var reducedDoubled = numbers.reduce(function (alreadyDoubled, x) {
  alreadyDoubled.push(x * 2);
  return alreadyDoubled;
}, []);
console.log('reduced doubled numbers', reducedDoubled);
// reduced doubled numbers [ 6, 2, 14 ]

refactor reduce to replace map

Let us refactor the callback passed to the Array.prototype.map method and see how to use the same callback function inside reduce

function by2(x) {
  return x * 2;
}
console.log('x 2', numbers.map(by2));
// x 2 [ 6, 2, 14 ]

To wrap this by2 function to be useful as a callback to reduce we can create utility function

function reduceMap(fn) {
  return function (mapped, x) {
    mapped.push(fn(x));
    return mapped;
  };
}
console.log('reduced x 2', numbers.reduce(reduceMap(by2), []));
// reduced x 2 [ 6, 2, 14 ]

reducing filter

Let us take Array.prototype.filter that creates a new array from items that return truthy value when passed through the callback function.

// filter < 5 numbers
function lessThan5(x) {
  return x < 5;
}
var small = numbers.filter(lessThan5);
console.log('small numbers', small);
// small numbers [ 3, 1 ]

Same feature implemented using reduce again returns a new array, just like map example above.

var reducedSmall = numbers.reduce(function (alreadySmall, x) {
  if (lessThan5(x)) {
    alreadySmall.push(x);
  }
  return alreadySmall;
}, []);
console.log('reduced small numbers', reducedSmall);
// reduced small numbers [ 3, 1 ]

refactor reduce to replace filter

Similarly to the map example, we can wrap the callback function to be usable inside reduce

function reduceFilter(fn) {
  return function (mapped, x) {
    if (fn(x)) {
      mapped.push(x);
    }
    return mapped;
  };
}
console.log('small numbers', 
    numbers.reduce(reduceFilter(lessThan5), [])
);
// small numbers [ 3, 1 ]

reducing some

Another operation that we can implement using reduce is Array.prototype.some that returns true if there is an item in the list for which the callback returns truthy value

// any number > 6?
function largerThan6(x) {
  return x > 6;
}
console.log('any number > 6?', numbers.some(largerThan6));
// any number > 6? true

Same feature using reduce has to go through each item (performance penalty), but can avoid evaluating the callback using short-circuit evaluation

console.log('reduced any number > 6?', numbers.reduce(function (found, x) {
  return found || largerThan6(x);
}, false));
// reduced any number > 6? true

refactor reduce to replace some

Let us wrap any callback to some to work for reduce

function reduceSome(fn) {
  return function (found, x) {
    return found || fn(x);
  };
}
console.log('reduced any number > 6?',
  numbers.reduce(reduceSome(largerThan6), false)
);
// reduced any number > 6? true

Bonus 1 - generalize each reduce transform

Let us take a look at each utility function that transforms a regular callback function into reduce-compatible function. I even add reduceEach that I implemented using ignore-argument utility function above

reduce adaptors

function reduceForEach(fn) {
  return function (whatever, x) {
    fn(x);
  };
}
function reduceMap(fn) {
  return function (mapped, x) {
    mapped.push(fn(x));
    return mapped;
  };
}
function reduceFilter(fn) {
  return function (mapped, x) {
    if (fn(x)) {
      mapped.push(x);
    }
    return mapped;
  };
}
function reduceSome(fn) {
  return function (found, x) {
    return found || fn(x);
  };
}

In all cases we maybe transform the previous value (called mapped or found) using the callback applied to the item's value x. Let us make each signature uniform, placing the original function first (preparing it for partial application). I will call these little functions reduce combinators.

reduce combinators

// forEach - the simplest case
function each(fn, prev, x) {
  fn(x);
}
function map(fn, prev, x) {
  prev.push(fn(x));
  return prev;
}
function some(fn, prev, x) {
  return prev || fn(x);
}
function filter(fn, mapped, x) {
  if (fn(x)) {
    mapped.push(x);
  }
  return mapped;
}

We can use this primitive combinators directly when calling reduce. For example here is the forEach equivalent.

function print(x) {
  console.log(x);
}
numbers.reduce(
  each.bind(null, print), 0
);
// 3 1 7

Similarly, we can call other methods using Array.prototype.reduce combinators

console.log('numbers * 2', numbers.reduce(
  map.bind(null, by2), []
));
console.log('numbers < 5', numbers.reduce(
  filter.bind(null, lessThan5), []
));
console.log('is there a number > 6?', numbers.reduce(
  some.bind(null, largerThan6), false
));

In each case we called numbers.reduce with a different adaptor and starting value.

Bonus 2 - curry each reduce combinator

The same boilerplate code to partially apply the callback function using Function.prototype.bind quickly becomes annoying. Let us apply the curry method to each function each, filter, etc.

curried reduce adaptors

var R = require('ramda');
var each = R.curry(function each(fn, prev, x) {
  fn(x);
});
// similar for filter, some, map

Now we can conveniently wrap a callback function. All we need to remember is the starting value

numbers.reduce(each(print), 0);
console.log('small numbers', numbers.reduce(filter(lessThan5), []));
console.log('some number > 6?', numbers.reduce(some(largerThan6), false));

Bonus 3 - remember the starting value

Remembering to pass 0 when using the each reduce adaptor, or false when using some adaptor quickly becomes a chore. Since functions in JavaScript are objects, we can store the initial value as a property. For example

var each = R.curry(function each(fn, prev, x) {
  fn(x);
});
each.start = 0;
var some = R.curry(function some(fn, prev, x) {
  return prev || fn(x);
});
some.start = false;
var filter = R.curry(function filter(fn, mapped, x) {
  if (fn(x)) {
    mapped.push(x);
  }
  return mapped;
});
filter.start = [];

then we don't have to remember how to start the reduce method

numbers.reduce(each(print), each.start);
console.log('some number > 6?', numbers.reduce(some(largerThan6), some.start));

Bonus 4 - on to transducers

Finally, why do we have to use the Array.prototype.reduce at all? We have to wrap the callback function and pass the starting value. We can create a new function that will take care of the wrapping and starting automatically.

// reducer function
function reducer(combinator, fn, list) {
  return list.reduce(combinator(fn), combinator.start);
}
var numbers = [3, 1, 7];
function print(x) {
  console.log(x);
}
reducer(each, print, numbers);
// 3 1 7

We are assuming that a combinator is our curried function that can transform the given callback and also has the start value. The reducer is so general now that it is almost a transducer!

Conclusion

Array.prototype.reduce is powerful, and every other Array method can be quickly reduced to using this list processing method. This is why it forms the basis for other functional solutions.

This makes a good interview question too, wink, wink.

Bonus 5 - querySelectorAll

Imagine we want to select multiple elements in the HTML document. I usually start with a simple list of selectors and for each selector grab an element

var selectors = ['#foo', '.bar']
var elements = selectors.map((selector) => {
  return document.querySelector(selector);
});
// [element1, element2]

The cardinality of selectors is the same as elements. What if each selector can potentially return many items? Then we get a list of lists!

var selectors = ['#foo', '.bar']
var elements = selectors.map((selector) => {
  return document.querySelectorAll(selector);
});
// [NodeList[element1a, element1b], NodeList[element2]]

Oh, and by the way, document.querySelectorAll returns NodeList, not an Array. Luckily we can easily convert it to an array using modern JavaScript.

var selectors = ['#foo', '.bar']
var elements = selectors.map((selector) => {
  return Array.from(document.querySelectorAll(selector));
});
// [[element1a, element1b], [element2]]

We probably want to flatten the returned list of elements, yet JavaScript does not have a built-in function to flatten arrays. We could use array concat method, but this requires an external variable

var selectors = ['#foo', '.bar']
var elements = []
selectors.forEach((selector) => {
  elements = elements.concat(Array.from(document.querySelectorAll(selector)));
});

Building a single data structure when iterating over the array like we are here is the best use case for reduce.

var selectors = ['#foo', '.bar']
const elements = selectors.reduce((all, selector) => {
  return all.concat(Array.from(document.querySelectorAll(selector)));
}, []);

Notice that we no longer have an external variable, and the returned result elements is declared constant.