New And Improved

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.


Pine Trees


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.1

With foldl in hand, we can look at its commutative and associative properties.

the commutative and associative properties

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 commutative, meaning that it makes no difference how we group the operations, we get the same result. But not all operators are commutative.

Subtraction is not commutative, 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 commutative, 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 right. But because we write:

valueToCompute = foldr(fn, valueToCompute, iterator);

return fn(current, valueToCompute);

The remainder of the compputation 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.2

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:3

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.4


Dr. Ian Malcolm, Jurrasic Park


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:5

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

  1. Languages like Haskell and Scheme that support tail call optimization can automatically transform linear recursion into a loop. Since loops are not difficult to write, that doesn’t seem like a big deal. But as we’ll see when we write foldr below, having two different functions share the same general shape communicates their design and relationship. Writing one as a loop and the other recursively conceals that which should be manifest. 

  2. Languages like Haskell that have lazy evaluation don’t need any special treatment to make this work, but since JavaScript is an “eager” language, we have to make some adjustments. 

  3. lazycons implements a linked list of sorts, with each conscell generator yielding a single value and then invoking a thunk to get a generator for the remainder of its values. This arrangement creates a lazily computed iterable that optimizes for the simplicity of prepending elements to the list. 

  4. The English phrase rule of thumb refers to a principle with broad application that is not intended to be strictly accurate or reliable for every situation. It refers to an easily learned and easily applied procedure or standard, based on practical experience rather than theory. This usage of the phrase can be traced back to the seventeenth century and has been associated with various trades where quantities were measured by comparison to the width or length of a thumb. –Wikipedia 

  5. There’s another consideration for code bases where for... of loops are unreliable because of the behaviour of Symbol shims, but this consideration is well outside the scope of this essay. Throughout this collection of essays, we presume that all features of ES2015 are available except for TCO.