# Learn To Fold Your JS Arrays

###
Neil Syiemlieh
*Updated on *
・5 min read

Folds (2 Part Series)

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:

```
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:

```
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:

```
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). 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—the current accumulation and the current array element—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.

```
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);
```

Notice how the reducer's interface must be `reducer(acc: B, x: A): B`

, which in this case, was

```
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 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).

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!

```
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, which we'll get into some other time. The examples from above now look like this, fat arrow style:

```
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:

```
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:

```
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));
```

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. 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—it works on any iterable object.
- 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). 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.

Folds (2 Part Series)

The whole way down the post I was asking myself "why not just use

`Array.reduce()`

and then you mentioned it at the end. 😂Succinct explanation though, and since AFAIK no widely used JavaScript engine implements tail call optimization it's likely that having a base folding function that uses a for loop instead of recursion will be necessary for data sets of a certain size.

Well done, though.