Reduce
Tags: javascript, functional
Published: 2019-05-18 14:35:55


Recently I needed to parse a semi-structured long text document and convert it into a data structure. As a lazy programmer I did not want to copy and paste the text a thousand times by hand. My solution was quite simple: read the document line-by-line, keep track of each line that I have not successfully parsed yet in an array, and try to parse the array at the end of each iteration, and empty the array every time parsing succeeds. And repeat till EOF.

This is how parsers work generally. My little hack was easy to do only because I contained my logic inside reduce function.

This experience reminded me that I have to write about the power and utility of reduce function.

Read this post if you are getting on board of functional programming train.

----

## Summing up Numbers

Let’s create a function to sum up the numbers inside an array. (you can try these snippets in your browser console)

```javascript
let oneToTen = [1,2,3,4,5,6,7,8,9,10]

let sum = function(arr) {
  let acc = 0 // the accumulated sum
  for(var i = 0; i < arr.length; i++) {
    let a = arr[i] // ith item in the array
    acc += a
  }
  return acc
}

sum(oneToTen)
```

Simple, yes! But like most things in programming, there is a nicer way for doing this:


```javascript
oneToTen.reduce((acc, a) => acc + a, 0)
```

`reduce` function is very powerful and it indeed looks magical if it is the first time you're seeing it.

Reduce is known by many other names: [Aggregate](https://docs.microsoft.com/en-us/dotnet/api/system.linq.enumerable.aggregate) in .NET Linq, fold in [Scala](https://medium.com/@mattmichihara/scala-folds-1989244d4fa4), foldl in [Haskell](https://wiki.haskell.org/Foldr_Foldl_Foldl'), [Erlang](http://erlang.org/doc/man/lists.html#foldl-3), [accumulate](https://www.geeksforgeeks.org/numeric-header-in-c-stl-set-1-accumulate-and-partial_sum/) in C++. Check the full list at Foldl [Wikipedia page](https://en.wikipedia.org/wiki/Fold_(higher-order_function)).

In JavaScript [Array.prototype.reduce](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce) receives two arguments. The first one is a function and the second argument is the initial value (or the seed) of the reduction process (here it is 0).

Here’s a more verbose version of the above code:

```javascript
oneToTen.reduce(function(acc, a) {
  return acc + a;
}, 0)
```

You can compare `acc` and `a` variables in this version with the similarly named variables in the loop version earlier.

So how does it work?

The function inside reduce (which we call reduction or aggregation function) gets called multiple times, exactly once per item in the array. This is very similar to the operation inside the body of for. At each step the reduction function returns the current accumulated value by summing up the previous accumulated value (`acc`) and the current item in the array `a`.

Let’s add some logs to see the result at each step:

```javascript
let oneToTen = [1,2,3,4,5,6,7,8,9,10]

oneToTen.reduce((acc, a) =>  {
  console.log(`acc = ${acc}, a = ${a}`)
  return acc + a
}, 0)
```

`reduce` is an abstraction over looping operations. We can convert any operation on arrays to reduce.

Probably counting the number of items in an array is one of the simplest and the most-common things that we do with arrays. JavaScript array natively support `Array.prototype.length`. But since it is an operation on arrays we can also use reduce to count the size of our array:

```javascript
['a', 'b', 'c', 'd', 'e'].reduce((acc, _a) => acc + 1, 0)
```

The length of an array does not depend on the actual value of each item in the array. That’s why we do not use the parameter *`_a`* in the above code.

Here the seed value of reduce is 0; reduce returns the seed value if the array that it is operating on is empty.

Of course you should continue using `Array.prototype.length` and most of the native array functions in your production code. Or use a library like [Ramda](https://ramdajs.com/). Many examples here are for demonstrating the generality and power of reduce function.

So far the reduce operations that we have seen produced a numeric result. Now let’s check string concatenation.

Standard `Array.prototype.join` concatenates an array of strings, using its argument and returns the concatenated string. We can also define it using reduce:

```javascript
['reduce', 'is', 'cool'].reduce((acc, a) => acc + ' ' + a, '')

// " reduce is cool"
```

Notice the extra space at the beginning of the string.

We have the extra space because we started reducing with an empty string. The value of the first `acc` is the initial empty string. Then in the reduction function we added a space and then the word `"reduce"`:

```javascript
['reduce', 'is', 'cool'].reduce((acc, a) => {
  console.log(`acc = '${acc}', a = '${a}'`)
  return acc + ' ' + a
}, '')

// " reduce is cool"
```

We can solve this easily by not passing any initial value to the reduce:

```javascript
['reduce', 'is', 'cool'].reduce((acc, a) => acc + ' ' + a)

// "reduce is cool"
```

But I argue that this implementation is also problematic because it fails for an empty array.

We can deal with the unnecessary space using an if expression. We check if acc is equal to the empty string (that means we are in the first iteration):

```javascript
['reduce', 'is', 'cool']
  .reduce((acc, a) => acc === '' ? a : acc + ' ' + a, '')
```

If you are not used to if-then-else expressions in JavaScript, the code above is equivalent to this:

```javascript
['reduce', 'is', 'cool'].reduce((acc, a) => {
  if(acc === '') {
    return a;
  } else {
    return acc + ' ' + a;
  }
}, '')
```

I prefer if-then-else expressions here because they ensure that I would not be forgetting the else clause. Every if in this tutorial will need an else.

I also always pass a seed value to reduce functions.

We can create the join function:

```javascript
function join(c, arr) {
  return arr.reduce((acc, a) => {
    if(acc === '') {
      return a;
    } else {
      return acc + c + a;
    } 
  }, '')
}

join('*', ['reduce', 'is', 'cool'])
```

Or more concisely:

```javascript
let join = (c, arr) => arr.reduce(
   (acc, a) => (acc === '' ? '' : acc + c) + a
 , '')
```

----

## Array functions

Let’s explore defining some basic array operations with reduce starting with **`map`**:

```javascript
let map = (f, arr) => arr.reduce((acc, a) => { 
  const mappedA = f(a) // apply f to the current item in the array
  return acc.concat([mappedA])
},[]) 

// the initial seed is an empty array, this is the result of reduction if the input array is empty

map(x => x * 2, oneToTen)

// [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
```

And **`filter`**:

```javascript
let filter = (f, arr) => arr.reduce((acc, a) => {
  const include = f(a)
  return include ? acc.concat([a]) : acc
}, [])

filter(
    x => x.startsWith('A')
  , ['Orange', 'Apple', 'Pearl', 'Avocado', 'Pomegranate']
)

// ["Apple", "Avocado"]
```

We can see the pattern now.

identity just creates array with the exact same elements of the array that it receives, without doing any other operation:

```javascript
let identity = arr => arr.reduce((acc, a) => acc.concat([a]), [])

identity(['a', 'b', 'c', 'd', 'e', 'f'])

// ['a', 'b', 'c', 'd', 'e', 'f']
```

Now let’s define reverse function using reduce. Check how its definition is different from identity:

```javascript
let reverse = arr => arr.reduce((acc, a) => [a].concat(acc), [])

reverse(['a', 'b', 'c', 'd', 'e', 'f'])

// ["f", "e", "d", "c", "b", "a"]
```

**`take`** returns the first N items in the array as a new array:

```javascript
let take = (howMany, arr) => arr.reduce(
   (acc, a) => acc.length === howMany ? acc : acc.concat([a])
 , []
)

take(3, ['a', 'b', 'c', 'd'])

// ['a', 'b', 'c']
```

**`head`** is a function that returns the first item in an array (similar to `arr[0]`). And last returns its last item of an array:

```javascript
let head = arr => arr.reduce((acc, *_a*) => acc)

let last = arr => arr.reduce((*_acc*, a) => a)

head(['a', 'b', 'c', 'd']) // "a"

last(['a', 'b', 'c', 'd']) // "d"
```

And a bit of sanity check:

```javascript
head(reverse(['a', 'b', 'c', 'd'])) === last(['a', 'b', 'c', 'd'])

// true
```

**`drop`** function removes the first N item in the array and returns the rest. We can define drop using take and reverse:

```javascript
let drop = (howMany, arr) => {
  const reversedArr = reverse(arr)
  const topN = take(arr.length - howMany, reversedArr)
  return reverse(topN)
}

drop(3, ['a','b','c','d','e']) // ["d", "e"]
```

This definition is not very efficient, because we iterate through the array three times: (`reverse`, `take`, `reverse`).

We can simply count the items in the array and exclude the items which their index is less than N:

```javascript
drop = (howMany, arr) => arr.reduce(
  (acc, a) => {
    // current index in array
    const currentIndex = acc.currentIndex + 1 

    const result = currentIndex >= howMany 
      ? acc.result.concat([a])
      : acc.result
    return {currentIndex, result}
  }
  , {currentIndex: -1, result: []} //the initial seed of aggregation
)
.result

drop(3, ['a','b','c','d','e']) // ["d", "e"]
```

Remember that JavaScript array index starts from 0.

Here the initial (seed) value of the reduction process is not a simple array or an empty string or number 0, but it is an object with two fields:

```javascript
{currentIndex: -1, result: []}
```

Note that the aggregation (reduction) function returns a similar object.

`currentIndex` keeps the count of the items in the array.

`result` keeps track of the result of our reduction process.

At the end of the reduction `currentIndex` is equal to the length of the array minus one and result contains the final result of the drop operation.

This implementation iterates through the array only once.

We can use de-structuring to make this function shorter and depending on your taste more or less readable:

```javascript
drop = (howMany, arr) => arr.reduce(
 ({ currentIndex, result }, a) => 
  currentIndex + 1 >= howMany 
   ? { currentIndex: currentIndex + 1, result: result.concat([a]) }
   : { currentIndex: currentIndex + 1, result: result }
 , { currentIndex: -1, result: [] }
).result
```
----

## The seed value

The idea of reducing using complex objects as seed values is very powerful. For example we can calculate the sum and the product of the items in an array simultaneously by going through the array only once:

```javascript
[1,2,3,4,5,6,7,8,9,10].reduce((acc, a) => {
  return {
    sum: acc.sum + a,
    product: acc.product * a
  }
}, {sum: 0, product: 1})
```

Here the choice of `{sum: 0, product: 1}` for initial seed is not trivial. `0` is the neutral element of sum operation and `1` is the neutral element of product.

The result of reducing an empty array is equal to the seed value of reduction.

```javascript
[].reduce((acc, a) => {
  return {
    sum: acc.sum + a,
    product: acc.product * a
  }
}, {sum: 0, product: 1})
```

Let’s study the choice of seed value for sum and product functions in more details:

```javascript
let sum     = arr => arr.reduce((acc, a) => acc + a, 0)
let product = arr => arr.reduce((acc, a) => acc * a, 1)
```

The idea is that the seed value i must be chosen so that for our reduction function `f` and for every `a` that is an element of our array:
> # f(a, i) == f(i, a) == a

Seed value is the neutral element of the reduction function.

For example for product function, where `f = (acc, a) => acc * a`, the seed value must be 1 so:

> 1 * a == a * 1 == a

## Pipe

`pipe` function receives a list of functions and applies them one after another to its input. By utilizing `pipe` we can avoid defining temporary local variables for one-time use:

```javascript
function addTwoPlusOneOverSeven(a) {
  const b = 2 * a
  const c = b + 1
  const d = c / 7
  return c
}

// will become

function addTwoPlusOneOverSeven(a) {
  return pipe([
      x => x * 2
    , x => x + 1
    , x => x / 7
  ])(a)
}
```

In other words, more generally pipe creates a new function by composing the functions in its input array:

```javascript
const addTwoPlusOneOverSeven = pipe([
    x => x * 2
  , x => x + 1
  , x => x / 7
])
```

Defining pipe using reduce is quite easy:

```javascript
let pipe = arr => arr.reduce(
    (acc, next) => x => next(acc(x))
  , x => x
)
```

Note the seed value `x => x`. This is identity function that is the neutral element of composition. It is akin to `0` for `sum` or `1` for `product`.

Here our reduction function is: `f = (acc, next) => x => next(acc(x))`

Note that `acc` and next are both functions and `f` compose them together one after the other.

`id = x => x` is the neutral element because for every function `h` that we can think of:


> f(id, h) == f(h, id) == h


```javascript
pipe([
    x => x * 2
  , x => x + 1
  , x => x / 7
  , x => `((10 * 2) + 1) / 7 = ${x}`
])(10)

// "((10 * 2) + 1) / 7 = 3"
```

----

## Moving Average

Lastly I want to show how we can implement efficient moving average, and some basic statistics using reduce:

```javascript
let movingAverage = (size, arr) => arr.reduce((acc, a) => {
  let currentWindow = acc.currentWindow.concat([a])
  currentWindow = currentWindow.length > size
    ? drop(1, currentWindow)
    : currentWindow
  return {
    currentWindow,
    result: currentWindow.length == size
      ? acc.result.concat([sum(currentWindow) / size])
      : acc.result
  }
}, {currentWindow: [], result: []})

let {result} = movingAverage(3, [2,5,6,4,1])
let expected = [sum([2,5,6])/3, sum([5,6,4])/3, sum([6,4,1])/3]

{result, expected}

// result = [4.333333333333333, 5, 3.6666666666666665]
```

Basic descriptive statistics in one-go:

```javascript
let stats = data => data.reduce( 
    ({count, sum, mean, vari, min, max}, x) => {
      const k = 1 / (count + 1)
      const mean_ = mean + k * (x - mean)
      const ssr_ = (count - 1) * vari + k * 
        count * (x - mean) * (x - mean)
      return {
          count: count + 1
        , sum: sum + x
        , mean: mean_
        , vari: ssr_ / Math.max(1, count)
        , min: isNaN(min) || x < min ? x : min
        , max: isNaN(max) || x > max ? x : max
      }
    }
  , {count: 0, sum: 0, mean: 0, vari: 0, min: NaN, max: NaN}
)

stats([3,4,2,2,4,3,2,2,4,5])

/*
{
  count: 10, 
  sum: 31, 
  mean: 3.1, 
  vari: 1.2111111111111112, 
  min: 2, 
  max: 5
}
*/ 
```

Here I am using [Welford variance algorithm](https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Welford's_online_algorithm) to compute the variance. This algorithm also works with streams.

We need to sort our array to calculate other statistics like median or quartiles.

----

## Defining Reduce

Now, to learn how reduce works internally, let’s define our own version reduce function.

reduce is an abstraction over recursion. At each iteration we produce the result by calling the reduction function `f` over the current element in the array and the result of of the latest iteration of the reduction.

```javascript
let reduce = (f, seed) => arr => {
  if(arr.length === 0){
    // result of reducing an empty array is the initial seed
    // the array is empty if it is the last iteration
    return seed 
  } else {
    const [a, ...tail] = arr
    const result = f(seed, a)
    
    // result is the initial seed of the next iteration
    return reduce(f, result)(tail)
  }
}

reduce((acc, a) => acc + a, 0)(oneToTen)

// 55
```

Or equivalently we can define reduce using iteration:

```javascript
reduce = (f, seed) => arr => {
  if(arr.length == 0) {
    // result of reducing an empty array is the initial seed
    return seed 
  } else {
    let result = seed
    for(var i = 0; i < arr.length; i++) {
      const a = arr[i]
      result = f(result, a)
    }
    return result
  }
}

reduce((acc, a) => acc + a, 0)(oneToTen)

// 55
```

I hope you agree that our definition using recursion is more elegant. It captures some truth about reduce. It clearly shows that reduce is an abstraction over recursion of the elements in an array.

The iterative version though is faster in JavaScript, because many JavaScript engines do not support [tail-call-optimization](https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-in-webkit/) technique.

## Reducing from Right

Standard `Array.prototype.reduce` reduces the array from left-to-right. This means it first applies the reduction operation to the seed value and the first element of the array, creates a new seed value, drops the first element and repeats.

We can also reduce arrays from right-to-left:

```javascript
let reduceRight = (f, seed) => arr => {
  if(arr.length === 0){
    // result of reducing an empty array is the initial seed
    return seed 
  } else {
    const [a, ...tail] = arr
    const result = reduceRight(f, seed)(tail)
    
    // first result is the seed, 
    // second result is f applied to the seed and 
    // the last element of the the array, ...
    return f(result, a)
  }
}

// 4 - (3 - (2 - (1 - 0))) = 2
let leftReduceResult  = [1,2,3,4].reduce((acc, a) => a - acc, 0)

// (((4 - 0) - 3) - 2) - 1 = -2
let rightReduceResult = reduceRight((acc, a) => a - acc, 0)([1,2,3,4])

console.log({leftReduceResult, rightReduceResult})
```

Right-to-left reduction is especially efficient with linked-list data structure.

ECMAScript supports [Array.prototype.reduceRight](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduceRight):

```javascript
[1,2,3,4].reduceRight((acc, a) => a - acc, 0)

// -2
```

----

## Scan

No piece of writing about reduce is complete without mentioning scan.

`scan` returns an array that contains the result of each step in reduction. Scan is especially useful in stream processing when we are dealing with effectively infinite streams (Check [RxJS scan](https://www.learnrxjs.io/operators/transformation/scan.html)).

```javascript
let scan = (f, x0) => arr => arr.reduce(
  ({prev, result}, a) => {
    const current = f(prev, a);
    return {prev: current, result: result.concat([current])};
  }
  , {prev: x0, result: []}
).result

let sum_scan = scan(
  (total, a) => total + a
  , 0
)

sum_scan(oneToTen)

// [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
```

Note that we used reduce to define scan while the final item in the array that scan produces is the result of reduce:

```javascript
last(scan(f, s, arr)) == reduce(f, s, arr)
```

Or using pipe:

```javascript
pipe([
  scan(f, s)
, last
]) == reduce(f, s)
```

Or in math notation:
> # last ∘ scan = reduce

I hope I got you into the zen of reduce.