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.

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:

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.