# Reductio and Abstract 'em

24 Feb 2017Oh, 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!*