What Can Array Folding Do?

This is Part 2 of the "Folds" series, where we look at how we could use the simple Fold pattern to perform a variety of array processing tasks.

What Was It Again?

In the previous article, we looked at how the fold works under the hood. Let's see it again as a recap:

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

It uses a for..of loop to traverse the list xs, reducing the list each time till we end up with just a single value. This programming pattern is very powerful. When I first learned about the fold, I was sceptical of how such a simple operation could do so much. But it turns out that a lot of problems in programming are reduction problems — we have a list of things and we want to extract a piece of information from that list.

Many of you might be familiar with Python's built-in functions sum, len and max. All these functions are essentially folds. I wanted to see how many more folds I could implement in JavaScript using just the function definition above. That would really demonstrate the various things this seemingly simple little function could accomplish. So below are different functions that we could create using the fold.

Keeping An Eye Out

I want to mention that in each fold shown below, there are two parts worth looking out for:

• The reducer: I've defined the reducer for each fold separately instead of inline, like the add reducer for the sum fold. The reducer is passed two arguments, acc and x. The data type of acc would be that of its inital value.
• The initial value: Notice how the initial value for every fold's accumulation is an identity with respect to the reducer. For example, 0 is the initial value used in the sum fold, because it is the identity under the add reducer. Remember that from the point of view of the reducer, the accumulation's initial value should essentially hold zero information. It should be void and useless, like how add sees 0 as having no information.

Behold, The Folds

sum

sum(xs: number[]): number

const add = (acc, x) => acc + x;
const sum = xs => fold(add, 0, xs);

The sum is probably the very first thing you think about when asked about collecting a list of values into one.

len

len(xs: any[]): number

const inc = (acc, x) => acc + 1;
const len = xs => fold(inc, 0, xs);

This is an emulation of the universally loved len, from Python. In the reducer, we ignore every element x, just adding a 1 instead.

product

product(xs: number[]): number

const mult = (acc, x) => acc * x;
const product = xs => fold(mult, 1, xs);

The product of a list of numbers. Having even a single 0 in xs would render this fold useless.

join

join(xs: any[]): string

const concat = (acc, x) => `${acc}${x}`;
const join = xs => fold(concat, '', xs);

This will concatenate a list of strings, or a list of anything, really! Injecting x into the template string invokes its .toString() method. So me saying that the declaration is join(xs: any[]): string, isn't specific enough. What I actually want is xs to be of type xs: A[] where A is a data type that returns a nicely formatted string when we call its .toString(). Without static typing, we can't do this in JavaScript. We see this feature in other languages though, like through Typeclasses in Haskell and Interfaces in TypeScript. Without it, JS would try to stringify x the default way, which might not work so well for more complex objects.

all

all(xs: boolean[]): boolean

const and = (acc, x) => acc && x;
const all = xs => fold(and, true, xs);

I really like how clean the all and some folds look. One problem though is that they don't do break out of the loop when the result becomes obvious. all([false, true, true, true]) will go through the entire list even though the result is known by the very first false.

some

some(xs: boolean[]): boolean

const or = (acc, x) => acc || x;
const some = xs => fold(or, false, xs);

maximum

maximum(xs: number[]): number

const max = (acc, x) => (x > acc) ? x : acc;
const maximum = xs => fold(max, -Infinity, xs);

maximum and minimum could be used on an array of any orderable data type, like JavaScript strings. But then we'd have to use the appropriate initial value. The one we used here, -Infinity, is only appropriate for an array of numbers.

minimum

minimum(xs: number[]): number

const min = (acc, x) => (x < acc) ? x : acc;
const minimum = xs => fold(min, Infinity, xs);

flatten

flatten(xs: any[][]): any[]

const concatArray = (acc, x) => [...acc, ...x];
const flatten = xs => fold(concatArray, [], xs);

This one has to be one of my favourites. There's a lot of array copying happening here. We could've mutated the acc using acc.push(...x) and returned it to avoid copying acc all the time, but you gotta admit, the spread operator looks much cleaner. This flattens an array one level deep, just like Lodash's _.flatten.

merge

merge(xs: object[]): object

const combine = (acc, x) => ({ ...acc, ...x });
const merge = xs => fold(combine, {}, xs);

The merge is very similar to the flatten, except it works on objects. It behaves just like JavaScript's built-in Object.assign.

reverse

reverse(xs: any[]): any[]

const prepend = (acc, x) => [x, ...acc];
const reverse = xs => fold(prepend, [], xs);

Another way we could've done this is mutate the acc using acc.unshift(x) (MDN) and return it instead of copying it through the spread operator.

Caveat: This fold's kind of an odd one out. Remember when I said that the accumulation's initial value was supposed to be an identity w.r.t. the reducer? Well, the one here, [], isn't. prepend([], x) will return [x]. According to Wikipedia's article on the fold:

One often wants to choose the identity element of the operation f as the initial value z.

There's no mention of a strict requirement for an identity element. So maybe some elegant mathematical rules would have to be broken in our messy programming world. Or maybe I just did an oopsie somewhere.

pipe

pipe(xs: { (x: any): any }[]): (x: any): any

const composeR = (acc, x) => {
    return m => x(acc(m));
};
const pipe = xs => fold(composeR, x => x, xs);

This one is my favourite. I might've butchered the type declaration for the pipe function here, so you'll have to forgive me. The thing I find interesting is initial value for the acc, x => x. It really drives home the idea that the initial value is an identity with respect to the reducer. As for the reducer, it is like the mathematical function composition, except in reverse.

The pipe takes in a list of unary functions and returns a function that runs them all in sequence. The returned value of each function is passed as the argument to the next.

last

const second = (acc, x) => x;
const last = xs => fold(second, null, xs);

I just found it fitting to put it at the end.

More Than Just A Fold

All the examples we've seen so far are folds — they take a list of things and return just a single thing. These next ones are not exactly folds in the same sense, but we can still implement them using the fold. That's right, map and filter can be made from the fold!

They don't just require an xs argument; they also need a function f. So the reducer must be defined inline, so we could capture the f through the reducer's closure. These examples also break the identity rule (see the reverse section above).

map

const map = (f, xs) => fold((acc, x) => [...acc, f(x)], [], xs);

filter

const filter = (f, xs) => fold((acc, x) => {
    return f(x)
        ? [...acc, x]
        : acc;
}, [], xs);

In both map and filter, we pass in the function f before xs, making them "iteratee-first, data-last". This is so that we could leverage the power of currying to make our code more modularized and composable.

Again, we could've mutated the acc using acc.push, but where's the elegance in that? It would go against the principle of immutability that FP preaches. I'm kidding of course, these are all just experiments. In an actual piece of software, we don't really want to get too functional in our own JS implementations, because JS isn't optimized for it (unless we absolutely know what we're doing). For that, we'd be better off using existing libraries like lodash/fp or Ramda.

A Playground

Every piece of code above has been included in this playground below. I also put in some examples of how we can use these folds together. A slight warning though: It looks very messy on a mobile screen.

const fold = (reducer, init, xs) => { let acc = init; for (const x of xs) { acc = reducer(acc, x); } return acc; }; // reducers const add = (acc, x) => acc + x; const inc = (acc, x) => acc + 1; const mult = (acc, x) => acc * x; const concat = (acc, x) => `${acc}${x}`; const and = (acc, x) => acc && x; const or = (acc, x) => acc || x; const max = (acc, x) => (x > acc) ? x : acc; const min = (acc, x) => (x < acc) ? x : acc; const concatArray = (acc, x) => [...acc, ...x]; const combine = (acc, x) => ({ ...acc, ...x }); const prepend = (acc, x) => [x, ...acc]; const composeR = (acc, x) => { return m => x(acc(m)); }; const second = (acc, x) => x; // folds const sum = xs => fold(add, 0, xs); const len = xs => fold(inc, 0, xs); const product = xs => fold(mult, 1, xs); const join = xs => fold(concat, '', xs); const all = xs => fold(and, true, xs); const some = xs => fold(or, false, xs); const maximum = xs => fold(max, -Infinity, xs); const minimum = xs => fold(min, Infinity, xs); const flatten = xs => fold(concatArray, [], xs); const merge = xs => fold(combine, {}, xs); const reverse = xs => fold(prepend, [], xs); const pipe = xs => fold(composeR, x => x, xs); const last = xs => fold(second, null, xs); // other things we could make through folding const map = (f, xs) => fold((acc, x) => [...acc, f(x)], [], xs); const filter = (f, xs) => fold((acc, x) => { return f(x) ? [...acc, x] : acc; }, [], xs); const A = [ [0, 1], [2, 3, 7, 8], [9, 13], [16] ]; // find the sum of each row of A b = map(sum, A); console.log('b:', b); // reverse each row of A and then flatten c = flatten(map(reverse, A)); console.log('c:', c); // get half of the absolute value of every number const nums = [3, -8, 6, 23, -100, 8, 1]; d = map(pipe([Math.abs, x => x / 2]), nums); console.log('d:', d); // filter out invalid words and make the remaining go UPPER!! const words = ['cat', 'sl2k3', 'dog', 'sn@k3', 'bird']; const validUpper = (ws) => { const validWords = filter(w => /^[a-z]+$/i.test(w), ws); const upper = map(x => x.toUpperCase() + '!!', validWords); return upper; }; e = validUpper(words); console.log('e:', e);

Like I said in my previous post, our way of implementing the fold is a hack.

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

We're using a for-loop and reassigning the acc variable, which isn't very respectful to the lords of immutability. We'll see how we could do that in the next article.

A few of the ideas for this article were inspired by the following:

• A Medium article on Folds
• The Folds section of Learn You a Haskell

Comments

[John]

Thanks Neil for your interesting article.

Sounds as if you may be interested in Ian Hofmann-Hicks youtube channel (search evilsoft on youtube) and his Crocks A.D.T library github.com/evilsoft/crocks

But, of course, you may have encountered his offerings before.

[Neil Syiemlieh]

Thanks! I had never heard of him but his content is exactly the kind of stuff I'm interested in. Reminds me of the Fantasy land spec I recently found

[John]

Enjoy!
I will look forward to further articles from you soon, I hope.

[Joshua Baker]

What's the benefit of doing this instead of just using the built in Array.prototype.reduce?

[Neil Syiemlieh]

There is not benefit other than exploring it for fun!

[diek]

I don't understand the pipe one, can you explain it better, or at least say examples of usage?

Ty.

[Neil Syiemlieh]

The pipe takes in an array of functions and "connects" them so that the output of a function within that array is passed as an input to the function after it.

// 
const squareThenIncrement = pipe([x => x * x, x => x + 1])
squareThenIncrement(4);  // 17
squareThenIncrement(9);  // 82

There are a few medium articles out there explaining it in more detail. I didn't want to make this post too detailed. I just wanted to show how much we could do using just that fold function