Reductio and Abstract 'em

Oh, hey, stranger! Long time no talk. In case you’re interested, I’ve moved house, job, and company since my last post, hence the hiatus. Sorry! Anyway, speaking of terrible segues, have you ever noticed that you can write every list function with reduceRight?

… Uh, no, you can’t?

Ok, bear with me: there are two caveats. For now, let’s assume two functions we get for free:

const head = ([x, ... xs]) =>  x
const cons = ( x,     xs ) => [x, ... xs]

Immediately, we can see that cons is really just a strange name for prepend. I’ll explain why we can take these for granted later, but it’ll make things much easier in the mean time to go with it. Until then, I promise it’s not a cop-out!

… Right, OK. You were saying?

Let’s start with everyone’s favourite list function: map. What’s cool about this function is that its accumulator is another list - we’re reducing one list to another!

const map = (f, xs) => xs.reduceRight(
  (acc, x) => cons(f(x), acc), []
)

// [2, 3, 4]
map(x => x + 1)([1, 2, 3])

Pretty neat, huh? With that realisation, it’s actually quite straightforward to implement everyone’s second favourite list function, filter:

const filter = (p, xs) => xs.reduceRight(
  (acc, x) => p(x) ? cons(x, acc)
                   :         acc,
  []
)

// [1, 2]
filter(x => x < 3)([1, 2, 3, 4])

Bam! If the condition be met, we cons the element. Otherwise, we just carry the accumulator through untouched. What about everyone’s third favourite list function: reduce? … Well, that’s a bit of a complicated one, so let’s build up to it.

Fine… but what about ____?

Name it and we’ll write it! Shall we start with append?

const append = (x, xs) => xs.reduceRight(
  (acc, h) => cons(h, acc), [x]
)

// [1, 2, 3, 4]
append(4)([1, 2, 3])

This reduceRight operation actually does nothing, but starts with a non-empty accumulator, which therefore just gets appended! With the same technique, we can write concat:

const concat = (xs, ys) =>
  xs.reduceRight(
    (acc, h) => cons(h, acc), ys
  )

// [1, 2, 3, 4]
concat([1, 2])([3, 4])

Anyway, now we have append, we can write reverse:

const reverse = xs => xs.reduceRight(
  (acc, x) => append(x, acc), []
)

// [3, 2, 1]
reverse([1, 2, 3])

This just takes each element from the end of the list and and sticks it to the end of the accumulator. Easy! Moving on, length is even simpler:

const length = xs => xs.reduceRight(
  (n, _) => n + 1, 0
)

// 4
length([1, 2, 3, 4])

This is all fun, but these aren’t mind-bending; chances are that you’ve already seen length written as a reduction at some point. Why don’t we try something harder? Let’s write elemAt, a function that returns the element at a given index. For example, elemAt(2, xs) is exactly the same as xs[2]. Oh yeah, that’s right: array access is a reduction.

const elemAt = (n, xs) => head(xs.reduce(
  ([e, n], x) => [n == 0 ? x : e, n - 1],
  [undefined, n]
))

// 3
elemAt(2, [1, 2, 3])

So, it’s a sneaky one: we count down the index until we hit 0, then “save” the value at that position. But wait! We used reduce, not reduceRight!

Well, ok, you could write this function with reduceRight, and I’ll leave that as a (quite tricky) exercise to the reader. However, it’s much easier to understand with reduce. Besides, if we can prove that reduce can be written with reduceRight, this isn’t cheating, is it?

const reduce = (f, acc, xs) =>
  xs.reduceRight(
    (accF, x) => z => accF(f(z, x)),
    x => x
  )(acc)

Serves you right for asking! The principle is that we reduce the list to a function to compute reduce. We start with x => x, which does nothing, and then tack on a new function for each element in the list. Let’s work it through with a simple(ish) example:

reduce((x, y) => x - y, 10, [1, 2])

  // Expand `reduce` to `reduceRight`
  == [1, 2].reduceRight(
       (g, x) => z => g(
         ((x, y) => x - y)(z, x)
       ),

       x => x
     )(10)

  // Simplify the reducer
  == [1, 2].reduceRight(
       (g, x) => z => g(z - x),
       x => x
     )(10)

  // Consume the first element
  == [1].reduceRight(
       (g, x) => z => g(z - x),
       z => (x => x)((x => x - 2)(z))
     )(10)

  // Simplify the ugly accumulator
  == [1].reduceRight(
       (g, x) => z => g(z - x),
       x => x - 2
     )(10)

  // Consume the next element
  == [].reduceRight(
       (g, x) => z => g(z - x),
       z => (x => x - 2)((x => x - 1)(z))
     )(10)

  // Simplify the ugly accumulator
  == [].reduceRight(
       (g, x) => z => g(z - x),
       z => z - 3
     )(10)

  // `reduceRight` on [] == acc
  == (z => z - 3)(10)

  // Evaluate
  == 7

We survived! That might take a couple of read-throughs, but the basic point is that our accumulator builds up a function that does each action in reverse. Of course, reduce and reduceRight calculate the same value for (x, y) => x - y, so try something like (x, y) => [x, y] to appreciate the difference.

Are you convinced yet? We can carry on with more examples if you- no? Well, ok. Let’s move onto why every list function is a form of reduceRight.

A (Strangely Familiar) List

A list can either be expressed as [] (empty) or [x, ... xs], a non-empty list - an item followed by another list*. This is exactly a linked list!

At this point, we can explain why we got cons and head for free earlier: all they do is construct and destruct lists in this form. They’re just ways to describe the structure of our list.

Int-reduce-ing Our Hero

Let’s write down two equations that define exactly how reduceRight works:

[].reduceRight(f, acc) = acc

[x, ... xs].reduceRight(f, acc) =
  f(xs.reduceRight(f, acc), x)

That’s all there is to reduceRight. An empty list reduces to its accumulator, a non-empty list reduces to f of the tail’s reduction and the head… The code is probably clearer than that sentence.

Now, because reduceRight lets us set empty and non-empty behaviour, and has an accumulator, we are free to change the shape of the list entirely. Note that we couldn’t write length in terms of map, because map doesn’t let us change the shape (length!) of a list. Similarly, we couldn’t write length in terms of filter, because filter doesn’t have an accumulator!

What reduceRight actually is, formally, is a catamorphism: a way of folding a type (in this case, a list) up into a value. The theory here is simple: if you have access to all possible configurations of your structure, you can do anything you like. If you don’t, you can’t!

reduce vs reduceRight?

Given that you can indeed express reduceRight in terms of reduce, it might seem odd to pick the less common one as a base operation. The answer lies in lazy languages and infinities, and there are already plenty of lazy reduceRight explanations online - you don’t need my poor attempt!

So… reduceRight can do anything with lists?

Yes! For some further reading, catamorphisms are also called folds, which does imply an unfold (an anamorphism - more wonderful names!), and Ramda’s unfold function can show you exactly what that does. Think about a function that produces a range - that’s unfolding a starting number into a list from 0 to the number! Still, we can think of that as not being a list function because it’s not a function on a list - it’s just a function that returns a list**.

tl;dr? When The Beatles said that all we need is love, they probably meant to say reduceRight.

That’s all from me! I should hopefully be more regular with my updates now I’m settled. See you next time!

Take care ♥

* Just as Peano numbers were either zero (Z) or one greater than some other Peano number (S Peano).

** If you’re a wincing mathematician, I’m sorry - this is a beginner’s guide!