The Accumulator Pattern

accumulator-to-reduce.md

.reduce()

• usage: occasionally
• purpose: loops over an array and reduces the elements into a single element
  • an application of the accumulator pattern
• returns the reduced item, one of several possibilities:
  • plain object - {}
  • Array - []
  • String - ""
  • Number - 1

The Accumulator Pattern

The accumulator pattern is a way of building up or accumulating data. The simplest example of the accumulator is a loop over an Array of numbers to sum their values. Here we are reducing an Array of number elements into a single number element.

Let's look at it from the imperative approach first.

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

let sum = 0;
for (let index = 0; index < numbers.length; ++index) {
  const number = numbers[index];
  sum = sum + number;
}

console.log(sum);

What if the loop-block were turned into a function? It takes in a number and the previous sum, and returns the new sum. In other words it receives an accumulator element and the next element in the array and returns the new accumulator element

const getNewSum = (previousSum, currentElement) => {
  return previousSum + currentElement;
}

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

let sum = 0;
for (let index = 0; index < numbers.length; ++index) {
  const number = numbers[index];
  sum = getNewSum(sum, number);
}

console.log(sum);

What if we turned the entire operation, both the loop and its inner block, into a function. What sort of arguments would it take? Think about the two variables that were defined outside the loop. One is an Array of number elements, and the other is an initial value for the accumulator (our sum).

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

const getNewSum = (previousSum, currentElement) => {
  return previousSum + currentElement;
}

const reduceSum = (arr, accumulatorCallback, initialValue) => {
  for (let index = 0; index < numbers.length; ++index) {
    const number = numbers[index];
    initialValue = accumulatorCallback(initialValue, number);
  }

  return initialValue;
}

let sum = 0;
const finalSum = reduceSum(numbers, getNewSum, sum);
console.log(finalSum);

With this final definition we are close to how the actual reduce() method functions. One major difference is it receives an Array passed as an argument whereas the reduce() method is called on an Array like numbers.reduce(...).

Let's take a look at what the function is doing. It receivs an Array to iterate over. It declares an accumulator variable (reassignable by let) and assigns it an initial value, in this case 0 for our sum accumulator. It then iterates over the Array and reassigns the previous sum to a new value derived from the previous sum and current element.

In other words it reassigns the accumulator value to what is returned by the callback function,getNewSum(). In this case we have defined the callback as adding the previous sum to the current number. But we could have easily defined it to have any other instruction.

All our reducer, reduceSum() is interested in is an Array of values and a callback that defines how accumulation should be evaluated.

As proof let's show how easy it is to swap in a new callback function that now calculates the product of the numbers in the Array. While also using the same reducer function to calculate the sum as we had before.

We'll leave all of the other logic the same besides generalizing our naming to get us closer to understanding reduce().

const elements = [1, 2, 3, 4];

const getNewSum = (previousSum, currentElement) => {
  return previousSum * currentElement;
}

const getNewProduct = (previousProduct, currentElement) => {
  return previousProduct * currentElement;
}

const reduceArray = (arr, accumulatorCallback, initialValue) => {
  for (let index = 0; index < elements.length; ++index) {
    const element = elements[index];
    initialValue = accumulatorCallback(initialValue, element);
  }

  return initialValue;
}

let initialProduct = 0;
const totalProduct = reduceArray(elements, getNewProduct, initialProduct);
console.log('product: ', totalProduct);

let initialSum = 0;
const totalSum = reduceArray(elements, getNewSum, initialSum);
console.log('sum: ', totalSum);

It should now be clear what reduce()'s purpose is: iterate over an Array and reduce its elements into a single element. In these cases we reduce an Array of numbers into a product and sum (number element). But we will see many more examples down the road that increase in complexity but provide an equal reduction of code.

Two key differences between our example and reduce() itself are the arr and initialValue parameters. When using our reduce() method we call it on the Array and the initial value is provided as an argument. However, the initial value does not get defined and assigned outside, you simply provide the value and the method takes care of managing assignment and reassignment while iterating. This helps us avoid external mutations of variables which is an anti-pattern.

Let's finally explore how the reduce() method works from its function signature to callback function. Reduce has a unique signature out of all the Array methods, it receives both a callback and initial value

• signature: (callbackFunction, initialValue)
• callbackFunction
  • signature: (previousAccumulatorValue, currentElement)
    • often abbreviated (prev, curr), (prevAcc, element), or (acc, e)
  • return: the new value of the accumulator
• initialValue: what will be accumulated
  • can be a Number, String, Object, Array, etc
  • if no value is provided the first element of the Array is used as the initial value and the iteration begins at the next element (index 1)

[].reduce(
  (previousAccumulatorValue, currentElement), // callbackFunction
  0, // initialValue 
);

// using our sum and product callbacks
const getNewSum = (previousSum, currentElement) => {
  return previousSum * currentElement;
}

const getNewProduct = (previousProduct, currentElement) => {
  return previousProduct * currentElement;
}

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

const sum = numbers.reduce(getNewSum, 0);
console.log(sum);

const product = numbers.reduce(getNewProduct, 0);
console.log(product);

// if you want to start at another number just pass it as the second argument
const productFromTen = numbers.reduce(getNewProduct, 10);
console.log(productFromTen);

Now that you've seen where reduce comes from and how it works conceptually let's see some more interesting use cases.

filtering

const filterEvens = (evenNumbers, number) => {
  if (number % 2 === 0) {
    evenNumbers.push(number);
    return evenNumbers;
  }

  return evenNumbers;
}

const numbers = [1, 2, 3, 4];
const onlyEvens = numbers.reduce(filterEvens, []);
console.log(onlyEvens);

Notice in this case that our accumulator is an Array rather than a number. To accumulate our Array we conditionally push new values into it. After pushing the even number into the evenNumbers we return this new accumulator value. In the odd case we simply return the current evenNumbers value since the number is not even (meaning it does not get accumulated).

However, it is a bad practice to mutate arguments or anything defined external to a function. This can lead to issues with external variables having unexpected values when they are used later in the code (because their reassignment is hidden in a function).

Instead it is best to make copies of arguments and operate on those. This is another reason Array methods are so useful - besides sort() and splice all of the methods return a copied Array, never affecting the original.

An easy way to avoid mutating the accumulator argument is to use the spread syntax of Arrays. Here we return a new Array each time which contains all the previously accumulated elements (through spreading), and the new element. The spread syntax ...Array spreads out all of the elements in the Array into the new Array surrounding it. By spreading we never change the value of the original Array but still retain our accumulator pattern.

This is just one of many uses of the spread operator. We will explore some of them later but if you want to learn more now here is a good place to start.

const filterEvens = (evenNumbers, number) => {
  // event, return the accumulator with the current even number
  if (number % 2 === 0) return [...evenNumbers, number];
  // not even, keep the current accumulator value and go to the next iteration
  return evenNumbers;
}

Let's look at reducing into an Object. The example is for a frequency counter of characters in a String. We will create an object with character: count properties to store our character frequencies.

const accumulateFrequency = (frequencies, character) => {
  const existingCount = frequencies[character]; // access the current character property in the frequencies object

  // if the character is already a property of the object this will be a count number
  if (existingCount) {
    frequencies[character] = existingCount + 1;
  } else { // if it is undefined then give it an initial count of 1
    frequencies[character] = 1;
  }

  // return the accumulated object
  return frequencies;
};

const string = 'what are the frequencies of these characters?';
const characters = string.split(''); // split into an Array of individual String character elements

const characterFrequencies = characters.reduce(accumulateFrequency, {});
console.log(characterFrequencies);

Method Chaining

For the final example let's see how reduce() can replace both a map() and filter() call. Our goal here is to multiply each number by 5 (map) and filter only the even results:

First let's look at how we could accomplish this by using map() and filter() chained onto each other. Method chaining is a way of calling one method "on" another by using the dot operator. This work so long as:

• what is to the left of the . is the correct type expected by
  • this can be a base value
  • this can be an expression that is evaluated to return a base value
• the method call to the right of the .

For example, say we call map() on an array: [].map.

To the left of the . is an Array type [] and to the right is an Array method map() that expects an Array to operate. This is valid syntax since both the left and right side of the . are of the correct types.

What if we called, or chained, filter() onto the map() call? map() returns an array (left of the .) and filter() expects an Array on the right of the . syntax.

This may seem confusing it will help to recall how JavaScript evaluates expressions.

First what is the statement in this case?

const mappedAndFiltered = [].map(mapCallback).filter(filterCallback);

Everything going on the right side of the assignment (=) as our expression. JavaScript will evaluate the expression from left to right until it reaches the end of the chain and returns that value.

An easy way to understand this is to break it apart into steps. Notice that after each step is evaluated whatever it returns is given to the next step. If we broke this apart into the evaluation steps this is what it looks like:

• statement: const mappedAndFiltered = [].map(mapCallback).filter(filterCallback);
• expression to evaluate (evaluation chain): [].map(mapCallback).filter(filterCallback);
• step 1: [] this is a base Array value, nothing to evaluate, firstArray
• step 2: firstArray.map() -> call map() on the Array to the left -> evaluate the map() method call -> returns an Array [], mappedArray
• step 3: mappedArray.filter() -> call filter() on the Array returned by the previous step -> evaluate the filter() method call -> returns an Array -> [], finalArray since it is the last step in the evaluation chain.
• step 4: the expression has been evaluated into an Array finalArray and is assigned to the variable mappedAndFiltered

So during each step of evaluation the method calls are converted into their return type (an Array). If we go from left to right we can see that each previous step returns the expected type (Array) needed by the next method call step.

Here is an example of how to reverse a String (a classic interview teaser). Notice that we are blending both String and Array methods in the chain. This may seem incorrect but remember each method is receiving exactly the type it expects.

We will chain 3 methods together that will: split the String into an array, reverse the elements of that Array, and finally join that (reversed) Array back together to make the reversed String:

const start = 'abcdefg';
const reversed = start.split('').reverse().join('');
console.log(reversed); // 'gfedcba'

Spread across multiple lines for readability:

const start = 'abcdefg';
const reversed = start
  .split('') // splits the String into an Array of invidiual character elements ['a', 'b', 'c', ...]
  .reverse() // reverse the order of the Array's elements ['g', 'f', 'e', ...]
  .join(''); // join the String elements of the Array back into a String

console.log(reversed); // 'gfedcba'

Let's break down the evaluation steps again to see why this works:

• expression: start.split('').reverse().join('');
• step 1: start this is a base String value, nothing to evaluate
• step 2: split('') call on the String value -> evaluate the method call -> returns an Array of String characters
• step 3: reverse() called on the Array returned by split() -> evaluate method call -> returns a reversed Array
• step 4: join() called on the Array returned by reverse() -> evaluate method call -> returns a String made up of the reversed String characters
• step 5: assign the reversed String to reversed

Now that we understand chaining let's see how it can be used to accomplish our goal:

const numbers = [1, 2, 3, 4];
const mappedAndFiltered = numbers.map(number => number * 5).filter(number => number % 2 === 0);

Let's split this into multiple lines to add some context. This is a common way of writing chained method calls so that each call takes up its own line and we can read it in order of evaluation. Note that JavaScript ignores the white space between each call.

const numbers = [1, 2, 3, 4];
const mappedAndFiltered = numbers // firstArray: [1, 2, 3, 4]
  .map(number => number * 5) // mappedArray: [5, 10, 15, 20]
  .filter(number => number % 2 === 0); // finalArray: [10, 20]

console.log(mappedAndFiltered); // [10, 20]

Because the filteredArray is the last returned value from the chain it becomes the value assigned to mappedAndFiltered.

Some people prefer to use chaining for readability. It reads pretty clearly, take some numbers and map (transform) them by the product of 5 then filter the result. However, consider the impact of large arrays. Remember that each iterative Array method iterates over the entire Array. So if we had an Array of length 10,000 elements. That means we have performed 10,000 iterations for the map() call and another 10,000 iterations for the filter() call. That's 20,000 iterations!

What if we were able to both transform and filter within one iteration? We would cut our processing time tremendously by removing the need for a second complete iteration. Enter our friend reduce() who, like the other iterative Array methods, iterates over the given Array. Using reduce() we can accomplish the same result but only using one iteration over the Aray.

// finalArray is our accumulator
// number is the current number element from the numbers array
const mapAndFilterCallback = (finalArray, number) => {
  const transformedNumber = number * 5; // inline or call the mapCallback here
  const isEven = transformedNumber % 2 === 0; // inline or call the filterCallback here

  // if it is even (passes our filter)
  // spread the previous elements and add the transformedNumber
  if (isEven) return [...finalArray, transformedNumber]; 

  // otherwise if it does not pass our filter
  // ignore (filter) this transformedNumber by just returning the finalArray
  return finalArray; 
};

const numbers = [1, 2, 3, 4];
const mappedAndFiltered = numbers.reduce(mapAndFilterCallback, []);

console.log(mappedAndFiltered); // [10, 20]

Get creative an try reducing some Arrays into different accumulator types. Remember that all the reducer cares about is a callback returning a new accumulator value and an initial accumulator object. It is entirely up to you what you define as accumulation and how you will store it as an accumulator.