DEV Community

Cover image for Forever Functional: The mighty reduce
OpenReplay Tech Blog
OpenReplay Tech Blog

Posted on • Updated on • Originally published at blog.openreplay.com

Forever Functional: The mighty reduce

by author Federico Kereki

Back in December 2009, ES5 (formally: ECMA-262 5th Edition) included several new functions and methods. The most important ones, from a functional programming (FP) point of view, were the trio (quartet?) formed by:

  • .map(...) that transforms one array into another by applying a given function to each of its elements, in order
  • .filter(...) that picks the array elements that satisfy a given condition
  • and two versions of a powerful method that we'll study here: .reduce(...) and .reduceRight(...). These functions apply an operation to a whole array (from left to right or from right to left) reducing it to a single result.

All these are "higher-order functions" (HOF) as we already saw in our Forever Functional: Higher Order Functions -- Functions to rule functions article. As we defined there, a HOF is a function that takes one or more functions as arguments. All the methods we listed above satisfy this, and using them allows you to code in a more declarative way. For instance, to select some elements from an array, you don't have to write out a loop, initialize a new output array, etc.: you write yourArray.filter(someFunction) and a new array will be produced with all the values from the original array that produce true when someFunction(...) is applied to them. Instead of specifying how to produce the result, step by step, you declare what elements interest you, and this FP-oriented method does the work for you.

What's interesting is that most of these methods are actually redundant. In fact, you can make do with just one: .reduce(...)! In this article, we'll study how to use it to emulate its siblings. That will give us an insight into their internal workings, and we'll also see techniques we may want to use elsewhere. Let's first get a reminder of how .reduce(...) works, and then get to use it as an alternative to the other methods.

Reducing an array to a value

The normal (recommended) way to use .reduce(...) is like yourArray.reduce(someFunction, initialValue). You can skip providing an initial value, but that may lead to errors down the line, so better don't. How does reducing work? The process is as follows:

  • initialize an accumulator with initialValue
  • set accumulator = someFunction(accumulator, yourArray[0])
  • then set accumulator = someFunction(accumulator, yourArray[1])
  • and then accumulator = someFunction(accumulator, yourArray[2])
  • ...going through all the array in order, doing the same, until its last element.

A very well-known example: if you had an array with numbers, you could add them up in a single line by writing yourArray.reduce((x,y)=>x+y, 0). The accumulator would start at zero (logical, for a sum). Then, each successive element of the array would be added to it. The final result would be the sum of all the elements of the array. Working in this way avoids all possibility of "off-by-one" errors, handles initialization and handling of results, and is side-effect free. (We discussed side-effect-free, pure functions in our Forever Functional: Injecting for Purity article.)

In usual FP-speak, .reduce(...) is known as "fold" or possibly "foldl" ("fold left") and .reduceRight(...) is "foldr" ("fold right").

Now, it may not be that obvious that .reduce(...) is good enough to mimic all the other methods. So, let's start with the simplest case, reducing from right to left.

Reducing from the right

The sibling of .reduce(...), .reduceRight(...) works exactly the same way, but instead of going through the array from the beginning to its end, it starts at the end and goes back to its beginning. For many things (like summing an array as we did above) this makes no difference but, in other cases, it might. How can we emulate this method? It will be easy!

The only difference, as we said, is that the array is processed in right-to-left order... so the simplest solution is (first) to reverse the array, and (second) reduce it to a value! We could almost write an "equation": yourArray.reduceRight(someFunction, initialValue) === yourArray.reverse().reduce(someFunction, initialValue)... but this has a problem; can you see it?

What's happening here? The key is that .reverse(...) is a mutator method -- it actually reverses the array in place. So, working in this way we'll get the same final result... But we'll have also have produced an unexpected side effect: the array will be reversed! The right way to do things is by generating a copy of the array first. We should write

yourArray.reduceRight(someFunction, initialValue) === 
[...yourArray].reverse().reduce(someFunction, initialValue)
Enter fullscreen mode Exit fullscreen mode

OK, why would we want to use this version? Short answer: we wouldn't! The conclusion we wanted is that .reduce(...) is capable by itself of emulating the alternative .reduceRight(...)... though, in this case, the solution doesn't seem to be worth the problem! As we said, this will be more of a sort of exercise in lateral thinking, finding new ways of doing things, and it's more about the way rather than the destination. Let's now see about the other methods.

Mapping an array

Going through a list of elements and performing some kind of transformation on them is a very common pattern in algorithms. When you start to learn how to program, writing such loops is a basic task. We can certainly process an array in that fashion, with a for(...) statement, but .map(...) lets us work functionally, in a more declarative way. A common example: with an array of persons with firstName and lastName attributes we could produce all full names with the following.

let fullNames = persons.map((p) => p.firstName + " " + p.lastName);
Enter fullscreen mode Exit fullscreen mode

When you write yourArray.map(aFunction) the result is that aFunction(...) (your "mapping function") is applied to every element of the array, thus producing a new array.

In math, a "map" is a transformation of values from a set into another one, like strings to numbers, objects to booleans, etc. In JavaScript, .map(...) transforms an array into a new one.

Can we simulate this process with .reduce(...)? The answer is "yes", and the solution is short. Given that we want to produce a new array, let's have an empty array as the initial value for reducing, and then add the mapped results to it, one at a time.

const mapByReduce = (yourArray, aFunction) => yourArray.reduce((a, v) => a.concat(aFunction(v)), []);
Enter fullscreen mode Exit fullscreen mode

Let's go through the code. We start with an empty array. Each element v of the array is given as the argument to the function, and the result is concatenated to the array a. When finished, the produced array will have the same result that applying .map(...) would have had -- once again, .reduce(...) proves its power! We wrote mapByReduce(...) as a function, but we could have added it to the Array.prototype if we wanted -- but why do this? We're studying the new implementation to add to our understanding of several methods, and not to (needlessly, I should say) replace them. Let's now consider the last method, filtering.

Open Source Session Replay

Debugging a web application in production may be challenging and time-consuming. OpenReplay is an Open-source alternative to FullStory, LogRocket and Hotjar. It allows you to monitor and replay everything your users do and shows how your app behaves for every issue.
It’s like having your browser’s inspector open while looking over your user’s shoulder.
OpenReplay is the only open-source alternative currently available.

OpenReplay

Happy debugging, for modern frontend teams - Start monitoring your web app for free.

Filtering an array

Filtering an array is somewhat similar to mapping in that a function is applied to each element of an array, but in this case it's used differently: if the function produces a "truthy" value, the corresponding element is selected and added to the result; if "falsy", the element is excluded. For example, with the same array of persons as in the previous example, if each had an age attribute, we could easily pick the adults.

let adults = persons.filter((p) => p.age >= 21);
Enter fullscreen mode Exit fullscreen mode

How can we emulate this? The solution is similar to that of mapping. We will start with an empty array, and after applying the filtering function to each element, we'll add it to the result if and only if the function produced a truthy value.

const filterByReduce = (yourArray, aFunction) => yourArray.reduce((a, v) => (aFunction(v) ? a.concat(v) : a), []);
Enter fullscreen mode Exit fullscreen mode

We use the ternary operator to decide, depending on the result of the function, whether to add or not the original element of the array to the final result. Once again, we've seen that .reduce(...) is powerful enough so you could use it as your only tool -- not that you'd want to, obviously, since the other methods already exist!

Summary

In this article, we've considered several basic FP methods, and we've seen that one of them, reducing, is powerful enough to emulate all others. This is, however, just an exercise -- why reinvent the wheel? The detail is that we've applied some interesting techniques, and learned more about how to use reducing in original ways, which you certainly may apply to your own code.

Top comments (1)

Collapse
 
totally_chase profile image
Phantz • Edited

Neat article. The supremacy of folds become stark in languages like Haskell. Their general usefulness, alongside their deep relation with monoids pose an incredibly interesting rabbit hole to dive into. It's not as useful in Javascript, unfortunately, but it's cool regardless.

I think you could extend the intuition on the relation between left fold and right fold. This is indeed a valid mathematical property of folds-

arr.reduceRight(f, z) === [...arr].reverse().reduce(f, z)
Enter fullscreen mode Exit fullscreen mode

But perhaps it'd be more useful to note that a no mutating reverse function can also be a fold.

function reverse<T>(arr: T[]): T[] {
    return arr.reduceRight((acc: T[], x) => [x, ...acc], []);
}
Enter fullscreen mode Exit fullscreen mode

The [x, ...acc] operation is, of course, cons. Reverse is just a right fold! It can also be a left fold using the append operation. So the property-

arr.reduceRight(f, z) === reverse(arr).reduce(f, z)
Enter fullscreen mode Exit fullscreen mode

could eta reduce to-

arr.reduceRight(f, z) === arr.reduceRight((acc: T[], x) => [x, ...acc], []).reduce(f, z)
Enter fullscreen mode Exit fullscreen mode

Which would be fold fusioned and optimized to oblivion. In Haskell, that is. Cool!

Anyway, this is the naive intuition we've all made when trying to find a relation between a left fold and a right fold. But you can go further. Right folds can lean so far right that they become left folds again.

Sounds like jargon right? Well this is how it works-

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldl accF initialVal target = foldr
    (\value abstractAccFn userAcc -> abstractAccFn (accF userAcc value))
    id
    target
    initialVal
Enter fullscreen mode Exit fullscreen mode

A right fold builds up functions, starting with id. Then the final build up function is applied to the user supplied initialVal and the order of operations ends up being left to right.

I know, dear reader, that it takes a bit to wrap your head around it but if you sit down one evening with a pen and paper and try to work through this, it'll feel like magic. In a good way. Once that's conquered, the next intuition to make is that the functions being built up represent endomorphisms. What the hell is an endomorphism then? Another rabbit hole to dive into :)

Here's the equivalent in typescript/javascript (the types may be an important resource in understanding abstract concepts).