What Can Array Folding Do?
Tags: javascript, beginners, functional, tutorial
Published: 2019-04-20 10:07:03

---
title: What Can Array Folding Do?
published: true
description: This is Part 2 of the "Folds" series, where we make our own fold from scratch and use it for various array processing tasks.
tags: javascript, beginner, functional, tutorial
series: Folds
cover_image: https://thepracticaldev.s3.amazonaws.com/i/qjuldpm88abzson9p3bg.jpg
---

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](https://dev.to/mebble/learn-to-fold-your-js-arrays-2o8p), we looked at how the fold works under the hood. Let's see it again as a recap:

```js
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 &mdash; 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`

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

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

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

```js
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](http://learnyouahaskell.com/types-and-typeclasses) and [Interfaces in TypeScript](https://www.typescriptlang.org/docs/handbook/interfaces.html). 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`

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

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

### __`maximum`__

`maximum(xs: number[]): number`

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

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

### __`flatten`__

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

```js
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](https://lodash.com/docs/4.17.11#flatten).

### __`merge`__

`merge(xs: object[]): object`

```js
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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/assign).

### __`reverse`__

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

```js
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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/unshift)) 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](https://en.wikipedia.org/wiki/Fold_(higher-order_function)#Special_folds_for_non-empty_lists) 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`

```js
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](https://en.wikipedia.org/wiki/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`__

```js
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 &mdash; 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`__

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

### __`filter`__

```js
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](https://medium.com/javascript-scene/curry-and-function-composition-2c208d774983) 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.

{% runkit

%}
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);
{% endrunkit %}

Like I said in my [previous post](https://dev.to/mebble/learn-to-fold-your-js-arrays-2o8p), our way of implementing the fold is a hack.

```js
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](https://medium.com/@zaid.naom/exploring-folds-a-powerful-pattern-of-functional-programming-3036974205c8)
- [The Folds section of Learn You a Haskell](http://learnyouahaskell.com/higher-order-functions#folds)