Church Numbers

06.01.2020 — Haskell, Math — 9 min read

A Hebrew version of the post can be found here.

Let's talk about numbers. Not about the "regular" numbers we all know, but about another representation of numbers – numbers in Church Encoding.
Church Encoding is a way of representing natural numbers as Higher‐Order Functions. Higher‐order function (HOF) is a function that receives functions as an input or returns a function as an output. They are functions that operate on functions.
Now that we understand what higher‐order functions are, let's define our encoding:
The encoding will match each natural number $n$ to a function, named $C_n$ , which works in this way:
$C_n$ receives two parameters: The first is a function name $f$ , which maps some element of type $T$ to some element of type $T$ . The second parameter is a value of type $T$ , named $x$ .
The function $C_n$ will return the outcome of operating $f$ on $x$ $n$ times in a chain. I.e. – the first iteration will run $f$ on $x$ , the next iteration will run $f$ on $f(x)$ and so on, $n$ times overall. If we want to write it formally, we will write it this way:

\begin{aligned} C_n(f,x) & =\underbrace{f(\ ...\ f(}_{\text{\textit n times}}x\underbrace{)\ ...\ )}_{\text{\textit n times}} \\ & =\underbrace{f\circ f \circ ...\circ f}_{\text{\textit n times}}(x) \\ & =f^n(x) \end{aligned}

To make things less abstract, let's look at some examples.
Let's choose $f(x)=2*x$ as $f$ , and so, in the next examples, the type $T$ we mentioned earlier, will be the Real Numbers ( $\R$ ).

$C_0$ is the function that will be matched, by Church Encoding, to the natural number $0$ . The result of $C_0(f,3)$ is $3$ . Why? Because we applied $f$ to $3$ zero times overall, I.e., we didn’t apply $f$ at all, and therefore we stayed with the original value, $3$ . Generally speaking, the function $C_0$ returns its second parameter for any function $f$ and any type $T$ .
The result of $C_1(f,3)$ is $f(3)=2*3=6$ .
The result of $C_2(f,3)$ is $f(f(3))=f(2*3)=2*(2*3)=12$ .

We now understand how the encoding maps a natural number to a HOF. Let's mark the function which maps a natural number $n$ to its corresponding $C_n$ HOF, as $C_E$ (E stands for encoding). We should now define the inverted mapping, from a HOF (that is guaranteed to represent a natural number in Church Encoding) to a natural number. Fortunately, the opposite direction is way simpler. We have a function named $C_h$ . We know it represents some natural number $h$ , but we don't know which number $h$ is. Therefore, we will calculate $C_h(f,x)$ for $f(x)=x+1$ as $f$ , and $0$ as $x$ . $C_h$ is going to apply $x+1$ to $0$ , $h$ times overall, and therefore our result will be $1*h=h$ as a result!

The mapping works in both directions! 🥳

We will name a HOF that was returned by $C_E$ a Church function, this is not a formal term, but it will make my sentences much shorter. 🙃 The inverted function, which maps a Church function to its original natural number, will be named $C_D$ (D stands for decoding).

Now, let's define addition and multiplication on Church Numbers. The operations should preserve the encoding. That means, we want to fulfill this equation: $C_E(n+m)=C_E(n)+C_E(m)$ . The notations here are a bit tricky: The plus sign on the left side represents an addition between two natural numbers. The sum of this addition is mapped to a Church function by $C_E$ .
On the right side, we apply $C_E$ to each number $n$ and $m$ separately, and then sum the results – the Church functions that represent $n$ and $m$ . The addition on the right hand isn't the regular addition for natural numbers; it's an addition between Church functions. Therefore, we'll define it as follows:
The result of $C_n+C_m$ should be the function $C_{n+m}$ , the Church function which takes two parameters, $f$ and $x$ , and returns $f$ applied to $x$ , $n+m$ times. Similarly, we will define the multiplication between Church functions: the result of $C_n*C_m$ will be $C_{n*m}$ .

In my opinion, this is a beautiful way to represents the natural numbers. The thing that Alonzo Church wants to show in this encoding is that we can solve any computable problem by using only functions as primitive types.
We shouldn't use this representation in practice, as it is much cheaper to represent numbers in memory as bits than as functions.
But it isn't going to stop us from doing so, as it will help us understand how the addition and the multiplication, which we defined earlier, actually work.

We are going to model our encoding in Haskell, which is an excellent language for this purpose since functions are primitive types in it, and it is straightforward to use it for writing functions which operate on functions.
Let's create a new type, named CNumber to hold a Church function. It's not actually a new type, but a wrapper for a higher‐order function that receives two parameters: a function which maps value from $T$ to a value from $T$ , and a value of $T$ . This $T$ can be any type, so $T$ is a generic parameter (or a type parameter) of this wrapped function. This is the way to write that in Haskell:

1{-# LANGUAGE RankNTypes #-}
2newtype CNumber = Nr (forall t. (t -> t) -> t -> t)

GitHub

The first line allows us to use the keyword forall, for defining an advanced generic function. On the second line, we define CNumber, saying its constructor is named Nr and that it receives a higher‐order generic function (which its generic parameter is t), of the kind we mentioned earlier.
I will remind you that in Haskell, the type a -> b -> c represents a function that takes a value of type a and a value of type b as its parameters and returns a value of type c.
The type we have created above, CNumber, is a container for a Church function. Please note that it doesn’t mean that every value of type CNumber is a Church function; it merely means that the container will match every HOF that receives a function and a value and returns a value.
Let's define $C_0$ , $C_1$ and $C_2$ :

1zero = Nr (\ f x -> x )
2one = Nr (\ f x -> f x )
3two = Nr (\ f x -> f (f x) )

GitHub

As we said earlier, $C_0$ , or zero, doesn’t apply f to x at all, and returns the $x$ . $C_1$ , or one returns the result of applying f to x once, and two returns the result of applying f to x twice in chain.
Assuming we have a CNumber that is guaranteed to hold a Church function, how can we recover the natural number it represents? We've already figured that out earlier, let's write it in Haskell:

1eval :: CNumber -> Int
2eval (Nr n) = n (+1) 0

GitHub

We used the function that the CNumber holds to apply (+1) – which corresponds to $f(x)=x+1$ that we talked about earlier – and 0, and so, we received the natural number that this Church function represents.

Now we'll define the addition function,
but before we do that, let's define a simpler function, named succ, that will help us implement the add function. succ increases any CNumber by one. I.e., succ zero returns one (the CNumber that represents $1$ ), succ one returns two, and so on.

1succ :: CNumber -> CNumber
2succ (Nr a) = Nr (\ f x -> f (a f x) )

GitHub

Given that succ receives a CNumber that represents $n$ , we define the result as a new function, which takes a function f and a value x. The new function is going to use a (the function that the given CNumber holds) to apply f to x $n$ times, and then apply f to the result once again. And so, we get the CNumber that represents $n+1$ .
An aside note: if you want this code to compile, you should replace import Prelude – which usually appears on the top of the code – with import Prelude hiding (succ), so the built-in function named succ doesn't collide with ours.
Now, it will be much easier to define addition! We want a function named add that receives two values of type CNumber and returns a CNumber that represents the addition of the Church functions that the parameters hold.

1add :: CNumber -> CNumber -> CNumber
2add (Nr a) (Nr b) = Nr (\ f x -> a f (b f x))

GitHub

We assume that a and b are Church functions that represents $n$ and $m$ , respectively. The function we wrote will use b to apply f to x $m$ times, and then use a to apply f to the result $n$ more times. Overall, the result function applies f to x $n+m$ times, as we aimed to.

But we can do better! We have the function a, which knows to apply a certain function $n$ times. Let's use it more smartly. We can apply succ to Nr b (the CNumber that holds a Church function that represents $m$ ) $n$ times, and so, we will get the CNumber that holds a Church function that represents $n+m$ .

1add :: CNumber -> CNumber -> CNumber
2add (Nr a) (Nr b) = a succ (Nr b)

GitHub

Yet there is an even a shorter way to write it, using partial applying:

1add :: CNumber -> CNumber -> CNumber
2add (Nr a) = a succ

GitHub

However, we aren’t trying to make our code shorter, but readable and simpler. 😊

All we have left to do is to define the multiplication function! Note that it's a great exercise, and in my honest opinion, it is worthwhile for you to solve it by yourself. Of course, if you prefer, you can go on and read my solution 🙃
We want to use a, in the same way we used it earlier, for calculating the result of the product of Nr a and Nr b.

1mult :: CNumber -> CNumber -> CNumber
2mult (Nr a) (Nr b) = a (add (Nr b)) zero

GitHub

Again, we assume that a and b are Church functions that represents $n$ and $m$ , respectively. The value of add (Nr b) is a function that receives a CNumber and adds Nr b to it. We use a to add Nr b to zero, $n$ times overall. As b is a Church function which represents $m$ , the total result will be a CNumber that holds a Church function which represents $n*m$ .

In the same way we can implement a power of Church functions!

1pow :: CNumber -> CNumber -> CNumber
2pow (Nr a) (Nr b) = b (mult a) one

GitHub

And we can go and define Tetration, but I think you get the idea. 😊