Functional programming in JavaScript (8)

Please take a look at other posts about functional programming in JavaScript:

1. Part 1 - what Functional Programming is about
2. Part 2 - Functional Pipelines
3. Part 3 - the Y Combinator
4. Part 4 - Monads
5. Part 5 - Trampoline
6. Part 6 - Lenses
7. Part 7 - Church encoding (booleans)
8. Part 8 - Church encoding (arithmetics)
9. Part 9 - Church encoding (if, recursion)
10. Part 10 - Church encoding (lists)

We continue the previous post on Church encoding. Please make sure you follow by quickly reading the basics.

So let's encode natural numbers. The idea here is to apply a function n-times to encode a natural number n. An auxiliray function to visualise numbers is exacly like "apply i => i+1 to 0 n times". Note how unusual this encoding is - numbers are not just "values", they are "processes". THREE is not just 3, it's a function applied 3 times.

const ZERO  = f => x => x;
const ONE   = f => x => f(x);
const TWO   = f => x => f(f(x));
const THREE = f => x => f(f(f(x)));

const toInt = n => n(i => i + 1)(0);

console.log( toInt( ZERO ) );
console.log( toInt( ONE ) );
console.log( toInt( TWO ) );
console.log( toInt( THREE ) );

ZERO, ONE, TWO, THREE, great but how do we continue? How to define a SUCC function that just computes n+1 from given n? That should be easy: "apply a function n times and just once again":

const SUCC  = n => f => x => f(n(f)(x));

const FOUR = SUCC(THREE);
console.log( toInt( FOUR ) );

Since this could be tricky here, how the SUCC actually work, let's try to symbolically perform some example computations. Everytime you feel unsafe later on, you can verify presented definitions in a similar way.

Let's check what's SUCC(ZERO).

SUCC is n => f => x => f(n(f)(x))

Here, n looks like a function since it's used in a term n(f). And indeed, since ZERO is f => x => x, we have:

SUCC(ZERO) = (n => f => x => f(n(f)(x))(f => x => x)

There seem to be a variable name collision and to avoid it, we rename variables in f => x => x to a => b => b (or anything else not containing n, f and x)

SUCC(ZERO) = (n => f => x => f(n(f)(x))(a => b => b) = (we substitute a => b => b for n) = ...

          ... = f => x => f( (a => b => b)(f)(x) ) = f => x => f( (b => b)(x) ) = f => x => f(x) = ONE

How do we define ADD and MUL? Well, ADD is "apply function n times and then m times". MUL is "apply n times (apply m times)".

const ADD   = m => n => f => x => m(f)(n(f)(x));
const MUL   = m => n => f => m(n(f));

console.log( toInt( ADD(TWO)(THREE) ) );
console.log( toInt( MUL(TWO)(THREE) ) );

That's impressive! POW is even simpler, we just apply m to n:

const POW = m => n => n(m);

console.log( toInt( POW(TWO)(FOUR) ) );

and if this one bothers you as too similar to MUL, you can rewrite it to make it explicit:

const POW = m => n => f => n(m)(f);

console.log( toInt( POW(TWO)(FOUR) ) );

Slow down and carefully consult the difference between MUL and POW.

Ready to continue? In the next post we'll define SUB and write our first complex function.