 # What Can Array Folding Do? Neil Syiemlieh Updated on ・8 min read

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],  ]; // 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:

### Discussion 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.

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

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

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

There is not benefit other than exploring it for fun!

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

Ty.

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

Dude. Please stop reinventing the wheel and do start reading the proper documentations.

Your "fold" is not a thing.

You are basically renaming and trying to hijack the credits from Array.prototype.reduce

And in case you didn't know it, the Array object also exposes methods like some(), every() that you called all(), join() etc.

You seem very well-versed in JS array methods. You're right, these functions are already available in the standard API. But why does that have to stop anyone from experimenting for the sake of learning? Relax

You are right, this is a very nice exercise to train. Comment marked as low quality/non-constructive by the community View code of conduct

Arrays folding can't be that complicated!!! Niel I think U should check yourself!!! Just too much stuff crammed together with out logistics logical reason. Just too much stuff running together and not really making much sense. It's kinda like U never learned any one thing. Sorry if I'm wrong. If wrong I apologized. If right there needs to be a fix. Smallest things together in one little group. Stick with one CPL. C#, Rust, Haskell, Python, html,css, JavaScript,One Computer Programming Language!!! Wiltel49@gmail.com

Array folding should never be this complicated, this was all just me experimenting with the idea. This post (along with most of my other posts) is just a way for me to solidify concepts that I recently learned while also having a way to improve my writing. So I might end up straying in my posts sometimes but that's kinda what makes it fun for me.

Great post and it was very interesting to see the depth you added in the code. Too often people just grab a higher order or a library to do the work without giving it a go to check fundamentals or a new approach. We would never innovate without this curiosity and I applaud your hard work on this and an excellent formed post 👍 Comment marked as low quality/non-constructive by the community View code of conduct

What are you talking about? Instead of rambling, come up with an improvement, cause it sounds like you're just full of shit.

Just a little harsh I think!  