The long way through Software Craftsmanship

A common misunderstanding about `reduce`

Dec 14, 2016 - 2 minute read - Comments - functional-programmingclojurehaskelljavascriptmisunderstandingreducefoldhigher-order-functionquotemozilla-developer-network

Misconception

I’ve read in several places that reduce reduces an array1 of values to a single one. The main characteristic of this function is not to reduce to a ‘smaller element’ / ‘single element’, but to have access to the accumulated results and the elements, one by one. Quoting Mozilla Developer Network’s (MDN) Javascript reference:

The reduce() method applies a function against an accumulator and each value of the array (from left-to-right) to reduce it to a single value.

Array.prototype.reduce() at MDN

Examples

Note: the examples in this article are in Javascript.

This is a simple example of such function:

> let sum = function (a, b) { return a + b; };
undefined
> [1,2,3].reduce(sum)
6

reduce can reduce a collection of elements to a single one. But this is not its defining characteristic. Let’s see another example:

> let append = function (element, accumulator) { accumulator.push(element); return accumulator };
undefined
> [1,2,3].reduce(append, [])
[ 1, 2, 3 ]

Note: this is a special case, where the elements are not altered by the reduce. Can be seen as the identity element for reduce.

This same behaviour can be reproduced with a map:

> let identity = function (x) { return x; };
undefined
> [1,2,3].map(identity)
[ 1, 2, 3 ]

An example that requires a reduce (and not a map) is frequencies. This function calculates the frequency of the elements in the collection:

> frequencies([3,3,2,1,-1])
{ '1': 1, '2': 1, '3': 2, '-1': 1 }

Why not a map? Because you need to cumulate the results.

> let frequency = function (accumulator, element) { 
  if (!accumulator[element]) {
    accumulator[element] = 0;
  } 
  accumulator[element]++;
  return accumulator; 
} 
undefined
> let frequencies = function (arr) {
  return arr.reduce(frequency, {});
}
undefined

Identity element: https://en.wikipedia.org/wiki/Identity_element


  1. In fact, any type in the Foldable class in Haskell. The reduce function in Javascript is in the Array prototype (only). In Clojure, a set, a map, an array, a list can be reduced. ↩︎

Self-Study in December 2016 Books read in 2016Q4