Learn To Fold Your JS Arrays
Tags: beginners, javascript, functional, tutorial
Published: 2019-04-08 11:45:05

---
title: Learn To Fold Your JS Arrays
published: true
description: Learn about the Fold, a powerful functional programming pattern, by making it from scratch
tags: beginners, javascript, functional, tutorial
series: Folds
cover_image: https://thepracticaldev.s3.amazonaws.com/i/u4l6427odar00i7u98kj.jpg
---

You might have come across a situation where you need to take an array of values and "collect" them. By this, I mean performing some operation on the array so we could obtain just a single value at the end. Below are a few examples.

You've definitely had to sum up an array of numbers before:

```js
function sum(numbers) {
    let acc = 0;
    for (const num of numbers) {
        acc = add(acc, num);
    }
    return acc;
}
```

Or get the product of an array of numbers:

```js
function prod(numbers) {
    let acc = 1;
    for (const num of numbers) {
        acc = mult(acc, num);
    }
    return acc;
}
```

Or find the largest number in an array of numbers:

```js
function maximum(numbers) {
    let acc = -Infinity;
    for (const num of numbers) {
        acc = max(acc, num);
    }
    return acc;
}
```

In each of these examples, we took an array of things and performed some operation that collected those things into a single thing.

# What Is A Fold?

The above examples have a few things in common. They all involve some very similar parts:

- A place that holds the final result, commonly referred to as the accumulation or `acc`
- An initial value for the accumulation (0, 1 and `-Infinity`)
- A binary operation that combines the accumulation and the array item we're currently working with (`add`, `mult` and `max`)

This process of collecting items clearly follows a pattern. We're currently repeating a lot of code, so if we could abstract it into a function, we'd have code that's much cleaner and more expressive. There's a name for such a function, the Fold ([Wikipedia](https://en.wikipedia.org/wiki/Fold_(higher-order_function))). This function is one of the fundamentals of functional programming. What we're going to do is implement the fold ourselves in JS, because why not?

## A Few Observations

There are three things regarding the fold that are worth noting.

The binary operations `add`, `mult` and `max` are called `reducers`. A reducer takes two values&mdash;the current accumulation and the current array element&mdash;and returns the new accumulation.

The initial value needs to be an `identity` with respect to the reducer. This means when the initial value is passed to the reducer along with another value `x`, the output is always `x`. Examples:
`add(0, x) = x`
`mult(1, x) = x`
`max(-Infinity, x) = x`.
Here, `0`, `1` and `-Infinity` are identities with respect to the reducers `add`, `mult` and `max`, respectively. We need it to be an `identity` because we want the initial accumulation to be "empty". `0` is empty w.r.t. summation and `1` is empty w.r.t. the product.

All array elements must be of the same data type (say type `A`), but the data type of the accumulation (say `B`) doesn't have to be the same as the datatype of the array elements. As an example, this code folds an array of numbers into a string.
{% runkit
// nothing
%}
const concatNum = (x, y) => x + y.toString();  // concatenates a string x and number y
const numbers = [1, 2, 3, 4, 5];  // elements are of type number
let acc = '';  // accumulation is of type string
for (const num of numbers) {
    acc = concatNum(acc, num);
}
console.log(acc);
{% endrunkit %}

Notice how the reducer's interface must be `reducer(acc: B, x: A): B`, which in this case, was

```ts
concatNum(acc: string, x: number): string
```

# Creating A Fold

That was a lot of talk. Let's finally make the fold. The fold is a higher order function (I highly recommend [Eloquent Javascript](http://eloquentjavascript.net/05_higher_order.html#h_xxCc98lOBK) for an HOF intro) that takes a reducer (a function), an initial value for the accumulation and an array (more formally a list, which is [what JS arrays are](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array#Description)).

We first generalise the add/mult/max reducer, calling it `reducer` (surprise!). We'll call the inital value `init`. We then generalise the array of things. It could be an array of anything, not just numbers, so we'll call it `xs`. We've now defined the fold!

```js
const fold = (reducer, init, xs) => {
    let acc = init;
    for (const x of xs) {
        acc = reducer(acc, x);
    }
    return acc;
};
```

Do you notice the order of the arguments into the fold? There's a reason we first pass in `reducer`, followed by `init` and then `xs`. It has something to do with [currying](https://medium.com/javascript-scene/curry-and-function-composition-2c208d774983), which we'll get into some other time. The examples from above now look like this, fat arrow style:

```js
const sum = xs => fold(add, 0, xs);
const prod = xs => fold(mult, 1, xs);
const maximum = xs => fold(max, -Infinity, xs);
```

Much better.

We can write the reducers inline if we want:

```js
const sum = xs => fold((acc, x) => acc + x, 0, xs);
const prod = xs => fold((acc, x) => acc * x, 1, xs);
const maximum = xs => fold((acc, x) => (acc >= x) ? acc : x, -Infinity, xs);
```

Here's an interactive editor for you to play with:
{% runkit
// nothing
%}
const fold = (reducer, init, xs) => {
    let acc = init;
    for (const x of xs) {
        acc = reducer(acc, x);
    }
    return acc;
};

const sum = xs => fold((acc, x) => acc + x, 0, xs);
const prod = xs => fold((acc, x) => acc * x, 1, xs);
const maximum = xs => fold((acc, x) => (acc >= x) ? acc : x, -Infinity, xs);

const numbers = [3, 7, 1, 2, 5];
console.log('sum:', sum(numbers));
console.log('product:', prod(numbers));
console.log('maximum:', maximum(numbers));
{% endrunkit %}

Pretty easy, right? Well, we kinda cheated. We used a for-loop (more specifically a for...of loop) in our fold definition, which is a big no-no in the functional programming world. Using a for-loop for data transformation means we're going to have to mutate some objects. Here, we mutated `acc` by reassigning it in the loop. A real functional implementation of the fold would use recursion and would avoid mutation. We'll explore that in another article.

### A Few Notes For The Interested

- JS already has a fold, which is a method available on arrays. It's called [reduce](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce). So I guess you could say re-implementing the fold ourselves was pretty pointless 🤷‍♂️ (although I hope it helps some FP newbie out there).
- Because we used a for...of loop instead of an ordinary for-loop, the fold we made works on more that just arrays&mdash;it works on any [iterable object](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols).
- In general, the fold should work on any source of enumerable data, like lists and trees.
- The idea of "collecting" doesn't have to be about combining the array elements, like addition or multiplication. It could be about "find and replace", like max/min reducers, or about "applying sequentially", like a function application reducer to pipe functions ([if you're interested](http://learnyouahaskell.com/higher-order-functions#function-application)). The applications are endless!

A function that takes a bunch of things to return just one thing might seem a little trivial, but we'll see how powerful it actually is by implementing many folds in the next article. We'll flatten arrays, pipe functions and [hopefully] do a lot more with the fold.