This essay originally appeared in 2017. Eagle-eyed readers pointed out that the original implementation of foldr had incorrect semantics. The essay has now been substantially revised to provide an implementation of foldr that is much closer to the one we find in lazy languages like Haskell.

When talking with people in the functional programming community, we often hear the term fold. Folding is an abstraction of operations to be carried out on linear collections, and it’s nearly always implemented as a higher-order function.

In this essay we’re going to look at what “folding” does by writing our own implementations. In addition to exploring its basic purpose, we’ll look at variations on folding that use different associativities (“left-associative folds” and “right-associative folds”) and explore the use of right-associative folds for performing lazy operations on possibly unbounded iterables.

By the end of the essay, we’ll have a basic grasp of common terms of art such as foldl and foldr, as well as a grasp of when each pattern should be applied–and when they cut against javaScript’s gran and should be eschewed in favour of simpler constructs.

Here we go.

preamble: Array.prototype.reduce

JavaScript has a method on arrays called reduce. It’s used for “reducing” a collection to a value of some kind. Here we use it to “reduce” an array of numbers to the sum of the numbers:

[1, 2, 3, 4, 5].reduce((x, y) => x + y, 0)
  //=> 15

Reduce folds the array into a single value. 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 operation on collections. 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

Let’s write our own fold, foldl:

let foldl = (fn, valueSoFar, iterable) => {
  const iterator = iterable[Symbol.iterator]();
  const { value: current, done } = iterator.next();

  if (done) {
    return valueSoFar;
  } else {
    return foldl(fn, fn(valueSoFar, current), iterator);
  }
};

foldl((valueSoFar, current) => valueSoFar + current, 0, [1, 2, 3, 4, 5])
  //=> 15

This is a recursive implementation. Thanks to almost every implementation of JavaScript punting on tail recursion optimization, there’s no easy way to write a version that doesn’t consume the stack in proportion to the number of elements being folded. Nevertheless, we’ll work with the recursive implementation for now.¹

With foldl in hand, we can look at its associative property.

the associative property

foldl consumes the elements from the left of the collection. 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.

When we write foldl((valueSoFar, current) => valueSoFar + current, 0, [1, 2, 3, 4, 5]), we’re computing the sum as if we wrote (((((0 + 1) + 2) + 3) + 4) + 5):

foldl((valueSoFar, current) => valueSoFar + current, 0, [1, 2, 3, 4, 5])
  //=> 15

(((((0 + 1) + 2) + 3) + 4) + 5)
  //=> 15

Addition is associative, meaning that it makes no difference how we group the operations, we get the same result. But not all operators are associative. For example, subtraction is not associative, we get different results depending upon how we group or order the operations:

(((((0 - 1) - 2) - 3) - 4) - 5)
  //=> -15

(0 - (1 - (2 - (3 - (4 - 5)))))
  //=> -3

Because subtraction is not associative, if we write an expression without explicitly forcing the order of operations with parentheses, we leave the order up to rules we arbitrarily establish about how we evaluate expressions.

How does JavaScript associate expressions by default? That’s easy to test:

0 - 1 - 2 - 3 - 4 - 5
  //=> -15

We say that JavaScript is left-associative, meaning that given an expression like 0 - 1 - 2 - 3 - 4 - 5, JavaScript always evaluates it as if we wrote (((((0 - 1) - 2) - 3) - 4) - 5)).

And likewise, we say that foldl is left-associative, because when we write foldl((valueSoFar, current) => valueSoFar - current, 0, [1, 2, 3, 4, 5]), we get the same result as if we wrote (((((0 - 1) - 2) - 3) - 4) - 5)):

(((((0 - 1) - 2) - 3) - 4) - 5)
  //=> -15

foldl((valueSoFar, current) => valueSoFar - current, 0, [1, 2, 3, 4, 5])
  //=> -15

But that’s not always what we want. Sometimes, we want to fold an iterable with right-associative semantics.

With right-associative semantics, 0 - 1 - 2 - 3 - 4 - 5 would be evaluated as if we wrote (0 - (1 - (2 - (3 - (4 - 5))))). And if we had a fold function with right-associative semantics–let’s call it foldr–then we would expect:

(0 - (1 - (2 - (3 - (4 - 5)))))
  //=> -3

foldr((current, valueToCompute) => current - valueToCompute, 5, [0, 1, 2, 3, 4])
  //=> -3

Note that with foldl, we supplied 0 as an initial value and [1, 2, 3, 4, 5] as the iterable, because we associate from the left. With foldr, we supplied 5 as the initial value, and [0, 1, 2, 3, 4] as the iterable, because foldr associates from the right, and thus the first thing we want it to evaluate will be 4 - 5.

Here’s foldr:

let foldr = (fn, valueToCompute, iterable) => {
  const iterator = iterable[Symbol.iterator]();
  const { value: current, done } = iterator.next();

  if (done) {
    return valueToCompute;
  } else {
    valueToCompute = foldr(fn, valueToCompute, iterator);

    return fn(current, valueToCompute);
  }
};

foldr((current, valueToCompute) => current - valueToCompute, 5, [0, 1, 2, 3, 4])
  //=> -3

We can see that like foldl, we consume the elements from the left. But because we write:

valueToCompute = foldr(fn, valueToCompute, iterator);

return fn(current, valueToCompute);

The remainder of the computation is evaluated first using recursion, and then its passed to the folding function fn. This is what makes it right-associative: Givien 0 - 1 - 2 - 3 - 4 - 5, it computes 1 - (2 - (3 - (4 - 5))) => 3 first, then returns 0 - 3 as the final result.

Although it consumes its elements from the left, foldr associates its operations from the right.

foldr also passes the arguments into fn in the opposite order from the way foldl. It’s easy to remember which function works which way: The argument representing the aggregated computation is on the left with foldl and on the right with foldr, which matches the associativity.

hard work pays off in the future;
laziness pays off right away

When we’re working with finite iterables, foldl can be used to implement map:

let mapl = (fn, iterable) =>
  foldl(
    (valueSoFar, current) => valueSoFar.concat([fn(current)]),
    [],
    iterable
  );

mapl(current => current * current, [1, 2, 3, 4, 5])
  //=> [1, 4, 9, 16, 25]

foldl is eager, meaning it computesmapl cannot be used on an infinite iterable. With care, we can make a fold that handles infinite iterables, but we begin with foldr rather than foldl.

What we’ll do is structure the code as with our eager version of foldr, but instead of passing the remainder of the computation to the folding function, we’ll pass a memoized of the remainder of the computation.

The folding function will explicitly invoke the thunk when it needs to evaluate the computation.²

This allows us to create a lazy foldr:

const memoized = (fn, keymaker = JSON.stringify) => {
    const lookupTable = Object.create(null);

    return function (...args) {
      const key = keymaker.call(this, args);

      return lookupTable[key] || (lookupTable[key] = fn.apply(this, args));
    }
  };

let foldr = (fn, valueToCompute, iterable) => {
  const iterator = iterable[Symbol.iterator]();
  const { value: current, done } = iterator.next();

  if (done) {
    return valueToCompute;
  } else {
    const toComputeThunk = memoized(
      () => foldr(fn, valueToCompute, iterator)
    );

    return fn(current, toComputeThunk);
  }
};

foldr(
  (current, toComputeThunk) => current + toComputeThunk(), 0, [1, 2, 3, 4, 5])
  //=> 15

foldr((current, toComputeThunk) => current - toComputeThunk(), 5, [0, 1, 2, 3, 4])
  //=> -3

Laziness won’t help us sum an infinite series, so we won’t try that. But we could use laziness to search a possibly infinite iterable:

let first = (predicate, iterable) =>
  foldr(
    (current, toComputeThunk) =>
      predicate(current) ? current : toComputeThunk(),
    undefined,
    iterable
  );

let fibonacci = function * () {
  let a = 0;
  let b = 1;
  let c;

  while (true) {
    yield a;

    ([a, b] = [b, a + b]);
  }
}

first(n => n > 0 && n % 7 === 0, fibonacci())
  //=> 21

It’s counter-intuitive that associating operations to the right makes working with infinite iterables possible, but foldr is quite explicit about separating the current value from the remainder of the computations to be performed, and since it consumes elements from the left, it can stop at any time by not evaluating the thunk representing the remainder of the computation.

And now to implement a lazy map. Our lazy map can take any iterable (whether bounded or unbounded) as an argument, and it always returns an iterable:³

const lazycons = (value, iterableThunk) => {
  return function * conscell () {
    yield value;
    yield * iterableThunk();
  }();
};

let lazymap = (mapper, iterable) =>
  foldr(
    (current, toComputeThunk) =>
      lazycons(mapper(current), toComputeThunk),
    [],
    iterable
  );

[a, b, c, d, e, f, g] = lazymap(c => c * c, fibonacci());

[a, b, c, d, e, f, g]
  //=> [0, 1, 1, 4, 9, 25, 64]

As we can see, the unique combination of consuming from the left and associating from the right makes the lazy version of foldr very useful for working with short-circuit semantics like first, or working with unbounded iterables like fibonacci.

what we’ve learned about foldl and foldr

As we’ve seen, the order of consuming values and the order of association are independent, and because they are independent, we get different semantics:

• Both foldl and foldr consume from the left. And thus, they can be written to consume iterables.
• foldl associates its folding function from the left.
• foldr associates its folding function from the right.
• Because foldr consumes from the left and associates from the right, a lazy implementation can provide short-circuit semantics and/or manage unbounded iterables.

In sum, the order of consuming values and the order of associating a folding function are two separate concepts, and they both matter.

We’ve also learned that foldl is best used when we want to eagerly evaluate a fold.

Likewise, we’ve learned that foldr’s semantics of consuming from the left but associating from the right make it ideal for lazy computations, such as working with short-circuit semantics or unbounded iterables. We are likely then to prefer to use the lazy implementation for foldr.

The penultimate “rule of thumb” is this: Use foldl for eager computations, foldr for lazy computations.⁴

just because we could, doesn’t mean we should

The examples in this essay were chosen to be simple enough that we could focus on the mechanisms of foldl and foldr. This helps us communicate with members of the larger programming community whose experience is grounded in orthodox functional programming.

However, writing all of our code as if we are thinking in Scheme/Haskell/ML and then translating those functions directly into JavaScript is often “cutting against the grain.” We initially wrote foldl recursively, but since most implementations of JavaScript cannot optimize linear recursion, we should usually implement foldl with a loop:⁵

let foldl = (fn, valueSoFar, iterable) => {
  for (const current of iterable) {
    valueSoFar = fn(valueSoFar, current);
  }

  return valueSoFar;
};

This implementation is faster and consumes less memory than the recursive implementation. Likewise, for working with lazy iterables, there are some benefits to the foldr approach, but for many linear higher-order operations on iterables, there are simpler higher-order functions we can write in a non-recursive style using iterators and generators.

We can map iterables lazily:

function * mapIterableWith (mapper, iterable) {
  for (const element of iterable) {
    yield mapper(element);
  }
}

[a, b, c, d, e, f, g] = mapIterableWith(c => c * c, fibonacci());

[a, b, c, d, e, f, g]
  //=> [0, 1, 1, 4, 9, 25, 64]

Filter iterables lazily:

function * filterIterableWith (predicate, iterable) {
  for (const element of iterable) {
    if (predicate(element)) yield element;
  }
}

first(n => n > 0 && n % 7 === 0, fibonacci())

[a, b, c, d, e, f, g] = filterIterableWith(n => n % 7 === 0, fibonacci());

[a, b, c, d, e, f, g]
  //=> [0, 21, 987, 46368, 2178309, 102334155, 4807526976]

And short-circuit semantics like first are also easy to write directly:

function first (predicate, iterable) {
  const [head] = filterIterableWith(predicate, iterable);

  return head;
}

first(n => n > 0 && n % 7 === 0, mapIterableWith(c => c * c, fibonacci()))
  //=> 441

The final rule of thumb is thus: Our code should make the simple things easy, and the complex things possible. Therefore, we write simple functions for mapping, filtering, or finding things in a lazy way, and we use tools like foldr when we encounter something that doesn’t neatly correspond to one of our simple tools.

(Discuss on /r/javascript)

Notes