Functional programming in JavaScript (7)

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)

One of the most beautiful examples of functional approach, that opens eyes and helps to understand basics, is the Church encoding. It's basically a way to encode operations and data types as functions; Church encoding encodes things in lambda calculus but here we are going to work with JavaScript.

Why is this even interesting? Encoding functions (operations) as functions sounds obvious. But encoding data types - booleans, numbers, lists (arrays/objects) as functions - basically means that we can build a world of computations that only contains functions, nothng else! It's not efficient, you wouldn't use it for real-world applications but it's really simple and has a really powerfull property: it's Turing complete which means that:

• you can store data (it has paris/lists)
• it does arithmetic (add/sub)
• it can make decisions (it has Booleans/IF)
• it can loop (or recurse infinitely) (it has the Y combinator)

Following the Church encoding in JavaScript is straightforward, at least at first. There are some technical difficulties later on, when IF is implemented. Before we begin, let's discuss this.

The IF will be a function of three arguments, IF(Condition)(ResultA)(ResultB). In some functional languages (like Haskell), function arguments are evaluated lazily, only if needed. When Haskell sees function arguments and some of them are not used in function definition, Haskell doesn't even try to evaluate them.

JavaScript instead computes arguments eagerly, all arguments are evaluated before the function is executed. If there's a recursion (possibly with another IF), JavaScript does a work that's not required, risking an infinite recursion.

Because of that, the Church encoding of some elements will differ in JavaScript comparing to how you'd encode things in Haskell.

Anyway, let's get started from basic building blocks.

const TRUE  = a => b => a;
const FALSE = a => b => b;

const AND = p => q => p(q)(p);
const OR  = p => q => p(p)(q);
const NOT = p => p(FALSE)(TRUE);

If you are new to this, that could be quite surprising, seeing even true and false encoded as functions. More, they are defined in a specific way, always taking one argument and possibly returning another function of one argument.

Is there a way to map TRUE and FALSE to plain JavaScript booleans, so that we can test and see how things work here? Well, just define a simple helper:

const toBool = f => f(true)(false);

and you can write few tests:

console.log( toBool( TRUE ) );
console.log( toBool( FALSE ) );

console.log( toBool( AND(TRUE)(TRUE) ) );
console.log( toBool( AND(FALSE)(TRUE) ) );
console.log( toBool( AND(TRUE)(FALSE) ) );
console.log( toBool( AND(FALSE)(FALSE) ) );

console.log( toBool( OR(TRUE)(TRUE) ) );
console.log( toBool( OR(FALSE)(TRUE) ) );
console.log( toBool( OR(TRUE)(FALSE) ) );
console.log( toBool( OR(FALSE)(FALSE) ) );

console.log( toBool( NOT(TRUE) ) );
console.log( toBool( NOT(FALSE) ) );

If you need some intuition: TRUE is a function of two arguments that just discards the second (try to think about TRUE as (a,b) => a) and FALSE is a function that takes two arguments and discards the first ((a,b) => b). Let's try to rewrite few of above examples then:

AND(TRUE)(TRUE) = T(T)(T) (because of how AND is defined) = T (because T discards second argument)

AND(TRUE)(FALSE) = T(F)(T) (because of how AND is defined) = F (because T discards second argument)

AND(FALSE)(TRUE) = F(T)(F) (because of how AND is defined) = F (because F discards first argument)

AND(FALSE)(FALSE) = F(F)(F) (because of how AND is defined) = F (because F discards first argument)

You can follow and rewrite OR and NOT, make sure you follow before moving forward. We'll continue in next post.