Reductio and Abstract 'em24 Feb 2017
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,
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
const append = (x, xs) => xs.reduceRight( (acc, h) => cons(h, acc), [x] ) // [1, 2, 3, 4] append(4)([1, 2, 3])
reduceRight operation actually does nothing, but starts with a non-empty accumulator, which therefore just gets appended! With the same technique, we can write
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
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. 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
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 == .reduceRight( (g, x) => z => g(z - x), z => (x => x)((x => x - 2)(z)) )(10) // Simplify the ugly accumulator == .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,
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
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
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.
reduce-ing Our Hero
Let’s write down two equations that define exactly how
.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 doesn’t let us change the shape (length!) of a list. Similarly, we couldn’t write
length in terms of
filter doesn’t have an accumulator!
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!
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!
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
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 (
** If you’re a wincing mathematician, I’m sorry - this is a beginner’s guide!