This content originally appeared on raganwald.com and was authored by Reginald Braithwaite
JavaScript has a method on arrays called reduce. It’s used for “reducing” a collection to a value of some kind.
For example, we can use it to “reduce” an array of numbers to the sum of the numbers:
[1, 2, 3, 4, 5].reduce((acc, n) => acc + n)
//=> 15
Another way to put it is to say that reduce folds the array into a single value.
If all we saw was stuff like summing the elements of arrays, we might think that “folding” is about taking a collections of things and turning it into just one of those things. Like turning an array of numbers into a number. But not so! Folding can produce any arbitrary value.
For example, mapping can be implemented as folding. Here we fold an array of numbers into an array of the squares of the numbers:
[1, 2, 3, 4, 5].reduce(
(acc, n) => acc.concat([n*n]),
[]
)
//=> [1, 4, 9, 16, 25]
And if we can map an array with a fold, we can also filter an array with a fold:
[1, 2, 3, 4, 5].reduce(
(acc, n) => n % 2 === 0 ? acc.concat([n]) : acc,
[]
)
//=> [2, 4]
Folding is a very fundamental kind of iteration over a collection. It can be used in many other ways, but let’s move along and talk about what kinds of collections we might want to fold.
foldl
.reduce is handy, but it’s not the whole story. It’s a method on arrays, and we might have lots of collections that aren’t arrays. We ought to be able to fold any iterable. Here’s a function that makes iterables:
const range = function * (fromNumber, toNumber) {
for (let i = fromNumber; i <= toNumber; ++i) yield i;
}
for (const n of range(1, 5)) {
console.log(n);
}
//=>
1
2
3
4
5
This can be useful, but it doesn’t work with .reduce:
range(1, 5).reduce((acc, n) => acc + n)
//=> range(1, 5).reduce is not a function.
So let’s write our own fold. We’re going to call it foldl:
function foldl (iterable, foldFunction) {
const iterator = iterable[Symbol.iterator]();
let { value: folded, done } = iterator.next();
while (!done) {
for (const element of iterator) {
folded = foldFunction(folded, element);
}
return folded;
}
}
foldl(range(1, 5), (acc, n) => acc + n)
//=> 15
This works with any iterable, including arrays:
foldl([1, 2, 3, 4, 5], (acc, n) => acc + n)
//=> 15
Note that it consumes the elements from the left of the collection. It has to, because iterables can only be consumed from the left. This is clear from range, because at the moment we write range(1, 5), none of the elements exist yet. It is only by taking them one by one that the next one is calculated.1
But foldl is not called foldl because it consumes its elements from the left. It’s called foldl because it associates its folding function from the left. To see what we mean, let’s do a fold where the order of association is very clear.
left-association
Let’s start with the idea of composing two functions, each of which takes one argument:
const compose2 = (x, y) => z => x(y(z));
Here are some examples of compose2 in use:
const half = x => x / 2;
const increment = x => x + 1;
const square = x => x * x;
compose2(half, increment)(3)
//=> 2
compose2(increment, square)(3)
//=> 10
compose2(half, increment) is the “half” of the “increment” of a number. In our case, that’s (3 + 1) / 2. Whereas compose2(increment, square) is the “increment” of the “square” of a number. In our case, that’s (3 * 3) + 1.
What about composing more than two functions? Before we write ourselves a “variadic” compose function, let’s be sure we agree what we mean. compose2(half, increment)(3) means half(increment(3)), so compose(half, increment, square)(3) will mean half(increment(square(3))).
Can we make compose out of compose2? Yes. If we want half(increment(square(3))), we can use compose2(compose2(half, increment), square)(3). And this generalizes! If we have four functions, a, b, c, and d, we can implement compose(a, b, c, d) with compose2(compose2(compose2(a, b), c), d).
Can we build a function by applying a function to other functions? Naturally, that’s one of JavaScript’s Good Parts™. And we know how to build a value by repeatedly applying a function to a collection of values, we use foldl:
const compose = (...fns) => foldl(fns, compose2);
compose(half, increment, square)(3)
//=> 5
So we can see what we mean by saying that foldl is “left-associative.” Given elements a, b, c, and d, foldl associates the folding function like this: (((a b) c) d). In the case of compose, it turns compose(a, b, c, d) into compose2(compose2(compose2(a, b), c), d).
foldr and right-association
We composed half with increment, then composed the result with square. Works like a charm. But that being said, it can be difficult to follow compose in programs. So sometimes, we want to apply the functions in order from left to right. This is called pipeline in JavaScript Allongé.
To make pipeline our of compose2, we want to associate the folding function from right to left. That is to say, given pipeline(half, increment, square)(4), we want to compose2 square with increment, and then compose the result with half, like this: compose2(half, compose2(increment, square)). There are a few ways to write pipeline without using a fold, but since we’re talking about folding, we’ll make pipeline with a fold.
foldl won’t do, because it associates the folding function from the left. What we want is the opposite, foldr. Here’s a recursive version:2
function foldr (iterable, foldFunction) {
const iterator = iterable[Symbol.iterator]();
let { value: first, done } = iterator.next();
if (!done) {
const foldedRemainder = foldr(iterator, foldFunction);
if (foldedRemainder === undefined) {
return first;
} else {
return foldFunction(foldedRemainder, first);
}
}
}
Although it consumes its elements from the left, thanks to the recursive call, it associates them from the right. Let’s check its behaviour:
const pipeline = (...fns) => foldr(fns, compose2);
pipeline(half, increment, square)(4)
//=> 9
We are indeed taking the half of four, incrementing that, and squaring the result. So while foldl is left-associative, (((a b) c) d), foldr is right-associative, (a (b (c d))). And if we write pipeline(a, b, c, d), we will get compose2(a, compose2(b, compose2(c, d))).
reduceRight
Right association is handy enough that JavaScript has something like it built in: .reduceRight. We can write pipeline with .reduceRight, because fns is an array:
const pipeline = (...fns) => fns.reduceRight(compose2);
pipeline(half, increment, square)(4)
//=> 9
.reduceRight is a method on arrays, and thus while it’s incredibly useful when we have an array to work with, it can’t be used on any arbitrary iterable. And while it makes no difference to writing functions like pipeline, it’s still instructive to realize that it differs from foldr in that it achieves right-association by consuming its elements from the right, unlike foldr, that consumes its elements from the left.
the bottom line
If we look at the implementation of foldr and think about stacks and recursion and so on, we can come to the conclusion that while foldr does associate the folding function from the right, it actually applies the folding function from the left, it’s just that we’ve used recursion and the call stack to reverse the order of elements.
This is true in a certain sense, but it’s really just an implementation detail. The point is to understand the semantics of foldl and foldr, and the semantics are:
- Both
foldlandfoldrconsume from the left. And thus, they can be written to consume iterables. foldlassociates its folding function from the left.foldrassociates its folding function from the right.
In sum, the order of consuming values and the order of associating a folding function are two separate concepts.
And our takeaway about reduce and reduceRight? They’re handy ways to fold arrays, but just arrays. When we want more, foldl and foldr are just a few lines of code. We can write them ourselves, or, if they are in a library, they’re easy to understand.
(discuss on /r/javascript)
notes
There’s more on the subject of left- and right-associations in Disambiguating Left-Association, Right-Association, and the Associative Property.
-
Like
.reduce,foldlis usually written to accommodate an optional seed. Feel free to rewritefoldlto allow for calls likefoldl(array, (acc, n) => acc + n, 0). ↩ -
This particular implementation does not work if the fold function ever deliberately returns
undefined. An implementation that gracefully accommodates this scenario is left as an exercise for the reader. ↩
This content originally appeared on raganwald.com and was authored by Reginald Braithwaite
Reginald Braithwaite | Sciencx (2017-04-10T00:00:00+00:00) A quick look at reduce, foldl, foldr, and associative order. Retrieved from https://www.scien.cx/2017/04/10/a-quick-look-at-reduce-foldl-foldr-and-associative-order/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.