reduce() is a Left Fold, But reduceRight() Isn't a Right Fold

When you finish this blog post you should be able revisit and understand this claim:

Javascript's Array.reduce() method is a left fold because it's left associative. Javascript's Array.reduceRight() is not a right fold, because it's not right associative. Instead, it's essentially Array.reverse().reduce(), which is left associative.

I came across a surprising Javascript implementation of reduce() and reduceRight() while studying functional patterns in Javascript.

What's a "Fold"?

A "fold" is a family of "higher order functions" (a function that takes a function as an argument) that take in a data structure and produces a single value.

The definition is vague because folding applies to many data structures and operations.

Javascript implements an array fold method, named ย Array.reduce().

It "reduces" (or "folds") an array into a single value by repeatedly applying a folding function.

For example: adding all the numbers in an array together, by folding the array "over" a function that adds its inputs together:

const add = (accumulator, element) => accumulator + element;
const result = [3, 5, 7, 9].reduce(add);

console.log(result); // logs 3 + 5 + 7 + 9, which is 24

Tracing the above code flow reveals why reduce() is a left fold.

First, the folding function is applied to the first elements of the array:

[3, 5, 7, 9]
 ๐Ÿ •  ๐Ÿ •
 โ”—--โ”ป---> We start with the first two elements
    
add(3, 5); // produces 8

Now we've accumulated these values together into 8.

The fold operation is repeated with the "accumulator" value (8), and next element in the array:

[3, 5,                  7, 9]
 ๐Ÿ •  ๐Ÿ •                   ๐Ÿ •
 โ”—--โ”ป-> Folded into 8   |
                    ๐Ÿ •   ๐Ÿ •
                    โ”—---โ”ป-> fold next element of into accumulator

add(8, 7); // produces 17

At each step, two values are "folded" or "reduced" into a single value, in this case by addition.

The operation repeats for as many elements as there are in the array.

At each step, we only fold two values together: the accumulator, and the next value of the array.

Array.reduce() is a "Left Fold"

Starting from the leftmost elements isn't what makes reduce() a "left" fold!

It's a left fold because the folding operation is left associative!

Expanding our fold, the eventual computation we perform is:

3 + 5 + 7 + 9

Computers can only perform one addition operation at a time.

What do we add first?

In our addition fold, 3 and 5 are added first, because reduce() is left associative:

((3 + 5) + 7) + 9

First we add 3 + 5. Then we add 7 to that result, and then we add 9 to that result.

If ย the operation were right associative, we'd add 7 + 9 first, then add 5 to the result of that, then 3 to the result of that:

3 + (5 + (7 + 9))

In our example, both the left and right associative examples produce the same sum.

That's because addition is a "commutative" operation: for addition (the "operator"), inputs ("operands") in any order produce the same result.

Associativity matters for other operators.

Subtraction is not commutative: 1 - (2 - 3) produces 2, while (1 - 2) - 3 produces -4.

foldl vs foldr

In Haskell and other functional languages, a left folding operation is called "foldl" (that's a lowercase "L") or simply "fold."

A right folding operation is called "foldr." This operation still starts from the left, but the folding operation is applied with right associativity.

Here's an example recursive foldr implementation in Javascript.

const foldr = (foldFn, [element, ...rest]) => {
  if (rest.length === 0) {
    return element;
  }
  return foldFn(element, foldr(foldFn, rest));
};

Side note: This implementation is a function that takes the array as a parameter, while reduce() is a method on the Array prototype that acts on the Array itself.

The important line above is the return statement.

It returns the fold operation, where the first input is the first element in the array, and the second input is the folded rest of the array.

With our example array [3, 5, 7, 9], the first operation it performs is 3 + <the complete fold of the rest of the array>.

The function recurses down to fold 7 + 9, then starts returning that up to the higher folds until the final result is produced.

You can test out foldr vs reduce in a Javascript console. For addition, reduce (foldl) and foldr should return the same result:

// For the add operation, reduce() and fodlr() should return
// the same result
const arr = [3, 5, 7, 9];

arr.reduce((acc, elem) => acc + elem); // prodcues 24

foldr((acc, elem) => acc + elem, arr) // produces 24

For subtraction, they should return different results, because subtraction isn't commutative:

// This should produce the same result as:
// ((3 - 5) - 7) - 9
arr.reduce((acc, elem) => acc - elem); // prodcues -18

// This should produce the same result as:
// 3 - (5 - (7 - 9))
foldr((acc, elem) => acc - elem, arr) // -4

foldr vs reduceRight()

Javascript has the array method reduceRight(). Given that reduce() is a foldl, it's natural to think that reduceRight() is a foldr.

However, reduceRight is so named because it starts from the right:

The reduceRight() method applies a function against an accumulator and each value of the array (from right-to-left) (emphasis mine)

Let's make this easier to follow by producing a string from our fold that represents the operation taking place.

Let's add parenthesis to the string to show the associativity taking place.

const arr = ['a', 'b', 'c', 'd'];
foldr((acc, elem) => `(${acc} + ${elem})`, arr)

// The above produces the string:
'(a + (b + (c + d)))'

This makes sense because it matches the right associativity we expect from a foldr.

The innermost grouping of parenthesis is on the right.

Now let's do the same for reduceRight():

arr.reduceRight((acc, elem) => `(${acc} + ${elem})`)

// The above produces the string:
'(((d + c) + b) + a)'

Note how the result is left associative!

The innermost grouping of parenthesis is on the left.

Also note that the first two elements, d and c are reversed.

This is because reduceRight starts from the last element, then performs a foldl over it.

reduceRight() is reverse().reduce()

We know that reduce() is left associative.

We can show reduceRight() is left associative, it just operates on a reversed array:

const arr = ['a', 'b', 'c', 'd'];

arr.reduceRight((acc, elem) => `(${acc} + ${elem})`)
// produces the string
'(((d + c) + b) + a)'

arr.reverse().reduce((acc, elem) => `(${acc} + ${elem})`)
// produces the same string
'(((d + c) + b) + a)'

When Would This Matter in Javascript?

Realistically, you won't often run into issues with .reduce() associativity when writing Javascript.

I came across this while working on the Shaderfrog GLSL compiler, a compiler written in Javascript for the 3D shading language "GLSL."

When parsing code, compilers must care about operator associativity.

I had to figure out when to do left and right associativity.

While researching folding, I found the misconception that reduceRight() was a right fold in two places:

Is reduce() really a "fold"?

"Folding" in functional programming extends beyond the implementation of .reduce().

Conceptually, the associativity of folding applies directly to .reduce() and is useful to understand the result of folding operations.

Otherwise, there are some significant differences:

  • Folding in functional languages is a recursive operation. Tail call optimization isn't available in all Javascript implementations, so we don't usually do recursive operations on lists as they can reach maximum recursion depth.
  • foldl in Haskell can cause a stack overflow(!) because it doesn't collapse the entire fold until it's evaluated, and each step of the fold is stored in memory until the fold is complete.

That's It!

Try going back to the beginning of this post to check your understanding.

If you want to try diving deeper into folding in Javascript, go through this kata.