Why reduce matters?
December 11, 2018Intro
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
Let’s start with defining an immutable linked list
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
And addition:
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 awhile
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
implementationconst arrToList = <T>(arr: T[]) => arr.reduce((l: List<T>, el) => append(l, el), Empty)

Another common term for
reduce
isfold
.
You can find code snippets used for this post here
Hi, my name is Simon Korzunov. I love reading about UI/UX related technologies and functional languages.