twopennycode

# Why reduce matters?

December 11, 2018

### Intro

When I started to learn “Redux” I was very confused with what “reducer” actually meant. I knew that there is an `Array` method called `reduce` that accepts a function with a similar signature, but not much else. In this post I will try to share what I discovered.

Disclaimer: I’m not an expert in Functional Programming, so whatever I say is just my attempt to digest it myself.

Now, let’s dive in!

### Linked list as an example

``````const Empty = null // give null precise meaning
type Opt<T> = T | typeof Empty // either a value or Empty
const isEmpty = <T>(v: Opt<T>): v is typeof Empty => v === Empty

// Element always has a value and maybe a reference to the prev
type Elem<T> = { val: T; prev: Opt<Elem<T>> }

// Either Empty or contains at least one element
type List<T> = Opt<Elem<T>>``````

Note that because of immutability we can only look at at the previous value. It means that we iterate newest -> oldest

### Define operations on it

Let’s try to implement `sum` and `findElement` functions:

`sum` would simply sum all numbers in a list:

``````const sum = (list: List<number>): number => {
let s = 0 // initial value

// iteration
let el = list
while (!isEmpty(el)) {
s = s + el.val // operation
el = el.prev
}

return s // result
}``````

`findElement` returns either the first element that satisfies the predicate or `Empty`

``````const findElement = (
list: List<number>,
pred: (v: number) => boolean
): Opt<number> => {
let res: Opt<number> = Empty // initial value

// iteration
let el = list

// terminate early if we found an element
while (!isEmpty(el) && isEmpty(res)) {
res = pred(el.val) ? el.val : Empty
el = el.prev
}

return res // result
}``````

Looks similar, right? Let’s try to extract the common parts into a separate function and name it `doStuff`

``````const doStuff = <R>(
list: List<number>,
operation: (res: R, n: number) => R,
initial: R
): R => {
let result = initial // initial value

let el = list
while (!isEmpty(el)) {
result = operation(result, el.val) // apply operation
el = el.prev
}

return result // result
}``````

Express `sum` and `findElement` via our new function.

``````//iterate over the list and perform (+) operation starting from 0
const sum = (list: List<number>) => doStuff(list, (s, num) => s + num, 0)``````

I love oneliners :)

``````const findElement = (list: List<number>, pred: (num: number) => boolean) =>
doStuff(
list,

// operation
(maybeResult, num) => {
// maybe we already found it
if (!isEmpty(maybeResult)) return maybeResult

// test the current value
return pred(num) ? num : Empty
},

Empty as Opt<number> // initial value
)``````

The operation function looks a little bit more involved, but conceptually it is pretty simple: it is a switch between “found it!” and “not yet” states. Once we found a value we cannot “unfind” it back.

Note that we lost early termination of `findElement`. But we did get a lot of code reuse in the process :)

Let’s give `doStuff` function a proper name and implement it via recursion

``````const reduce = <T, R>(l: List<T>, op: (r: R, v: T) => R, initVal: R): R =>
// if list is empty return what we currently have
// otherwise compute the result of the list minus last element
// and apply operator to the result and to the current element value
isEmpty(l) ? initVal : op(reduce(l.prev, op, initVal), l.val)``````

Note that this form iterates in the right order: oldest to newest. Exactly what we wanted and we are not mutating anything in the process!

### We have the superpower

It appears that reduce is a general abstraction over iteration. You can probably think about it as a `for` loop but without any unnecessary ceremony.

Now, let’s try to feel the power and build `map` and `filter` functions. But first we need a way to actually grow lists.

``````// adds an element to the end of the list
const append = <T>(l: List<T>, val: T): List<T> => ({ val, prev: l })``````

operator for `filter` is pretty straightforward: “if I like you then welcome aboard, please next otherwise”.

``````// filter out elements that don't satisfy the predicate
const filter = <T>(list: List<T>, pred: (v: T) => boolean): List<T> =>
reduce(list, (r: List<T>, el) => (pred(el) ? append(r, el) : r), Empty)``````

`map` is a function that accepts a list and a function that transforms each element into something else (for example: `const f = (n: number) => n.toString()`).

``````const map = <A, B>(list: List<A>, f: (a: A) => B): List<B> =>
reduce(list, (r: List<B>, el) => append(r, f(el)), Empty)``````

That was easy! Maybe something more challenging? Something like pairwise rxjs operator.

In short, we need to form pairs out of a sequence of elements. For examples: `[1,2,3,4]` would become `[[1,2], [3,4]]`. And if we have an odd number of elements we would have one “outsider” left: `[1,2,3]` -> `{pairs: [1,2], left: 3}`.

``````// list of full pairs plus optional tail if the length is odd
type PairwiseRes<T> = { paired: List<[T, T]>; left: Opt<T> }

// a helper to make typescript happy with [T,T] type
const pair = <T>(a: T, b: T): [T, T] => [a, b]

const pairOperator = <T>(
{ pairs, left }: PairwiseRes<T>,
el: T
): PairwiseRes<T> =>
isEmpty(left)
? // wait for the next
{ pairs, left: el }
: // we have two
{ pairs: append(pairs, pair(left, el)), left: Empty }``````

When the operator sees a value it acts like so: “do I have one already? If so form a pair, wait for the next otherwise”.

``````const pairwise = <T>(list: List<T>): PairwiseRes<T> =>
reduce(list, pairOperator, { pairs: Empty, left: Empty })``````

Again, when we have a recipe what to do with elements one by one, actually applying it to the list is super easy.

### What about `Array.prototype.reduce`‘?

The best part is that all our operators would just work with Array too (and with all other collections that support `reduce`).

``````const arr = [1, 2, 3, 4]
arr.reduce(pairOperator, {
pairs: Empty,
left: Empty
})
//  pairs:{"val":[3,4],"prev":{"val":[1,2],"prev":null}},
//  left:null

pairwise(arrToList(arr))
//  pairs:{"val":[3,4],"prev":{"val":[1,2],"prev":null}},
//  left:null``````

``````const add = (a: number, b: number) => a + b

const arr = [1, 2, 3, 4]
const list = arrToList(arr)

reduce(list, add, 0) // 10
arr.reduce(add, 0) // 10``````

### Summary

I hope, that next time you would write a “reducer” or simply use `arr.reduce` you would appreciate this superpower a little bit more.

P.S.

• redux is a form of this pattern. You can think about actions as a collection of events happening overtime, where “reducer” itself is an operator.

• Our `reduce` implementation is not a tail recursion, which means that you cannot replace it with just a `while` loop (bad for performance). In practice, you iterate newest -> oldest, but before/after you reverse the list back with something like:

``````const reverse = <T>(l: List<T>): List<T> =>
isEmpty(l) ? l : { val: l.val, prev: reverse(l.prev) }``````
• `arrToList` implementation

``````const arrToList = <T>(arr: T[]) =>
arr.reduce((l: List<T>, el) => append(l, el), Empty)``````
• Another common term for `reduce` is `fold`.

You can find code snippets used for this post here

Back to the list.

Hi, my name is Simon Korzunov. I love reading about UI/UX related technologies and functional languages.