## DEV Community is a community of 665,273 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # What Can Array Folding Do? Neil Syiemlieh
Just starting my tech journey. Engineer at Gojek.

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 (15) 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. Dieg Oto

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

Ty. Neil Syiemlieh • Edited

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 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 Neil Syiemlieh

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. ImTheDeveloper

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
Carl-Erik Kopseng

What are you talking about? Instead of rambling, come up with an improvement, cause it sounds like you're just full of shit. Comment marked as low quality/non-constructive by the community. View Code of Conduct

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. Neil Syiemlieh

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