Encode boolean values and operations with pure functions

Computerphile has a really good video that covers the fundamental ideas of lambda calculus, which is the basis of most functional programming languages. One of the example it went throught is encoding boolean values (true/false) using pure functions - it really bended my mind.

The fundamental idea of a boolean value is making a choice. So, the encoding of boolean values encode that idea! The true value can be encoded as a function that takes two inputs, x and y, and return the first input, x, that is, it chooses the first input. Likewise, the false value takes two inputs and chooses the second input:

true <- structure(function(x, y) x, class = c("true", "bool"))
false <- structure(function(x, y) y, class = c("false", "bool"))

# add a print method so they display nicer
print.bool <- function(x) cat(class(x)[1], "\n")

That’s it.

true
## true
false
## false

Next let’s define logical operations on them. The first one that comes to one’s mind is perhaps negation. This is perhaps a little mind bending for the first time, but here it goes:

# `!` is a generic function in r, so we can add methods to it
`!.bool` <- function(x) x(false, true)

Remeber that the boolean values are functions and the true value chooses it’s first input. In the above definition of negation, we simply set the first input to false, so true chooses false, and we set the second input to true so false chooses true - and that’s negation!:

!true
## false
!false
## true

The video left a little puzzle to solve: how to define other logical operations in this style, such as AND, OR and XOR? So I had a go and totally bended my mind (and the definition is so simple!):

AND is basically a function that uses it’s first input to choose between the second input and false

# `&` is generic 
`&.bool` <- function(x, y) x(y, false)

true & true
## true
false & true
## false
true & false
## false
false & false
## false

OR is a function that uses it’s first input to choose between true and the second input:

# `|` is generic 
`|.bool` <- function(x, y) x(true, y)

true | true
## true
false | true
## true
true | false
## true
false | false
## false

XOR is a function that uses it’s first input to choos between the negation of the second input and false:

# `xor` is generic 
xor.bool <- function(x, y) x(!y, false)

xor(true, false)
## true
xor(false, true)
## true
xor(false, false)
## false
xor(true, true)
## false

Pretty sure there’re other definitions, but I’m just totally mind blowed by this style of thinking. Perhaps next question is, how to define integer and integer operations in this functional style? And how about floating numbers, characters etc? Recently I learnt a few functional programming languages and techniques and it really bends my mind and broadens my view a lot. I’m hoping to learn more and share more!