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 thesum
fold. The reducer is passed two arguments,acc
andx
. The data type ofacc
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 thesum
fold, because it is the identity under theadd
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 howadd
sees0
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.
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:
Top comments (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.
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.
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
functionSome comments may only be visible to logged-in visitors. Sign in to view all comments.