Skip to content

Church Numbers

Haskell, מתמטיקה

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 nn to a function, named CnC_n, which works in this way:
CnC_n receives two parameters: The first is a function name ff, which maps some element of type TT to some element of type TT. The second parameter is a value of type TT, named xx.
The function CnC_n will return the outcome of operating ff on xx nn times in a chain. I.e. – the first iteration will run ff on xx, the next iteration will run ff on f(x)f(x) and so on, nn times overall. If we want to write it formally, we will write it this way:

Cn(f,x)=f( ... f(n timesx) ... )n times=ff...fn times(x)=fn(x)\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)=2xf(x)=2*x as ff, and so, in the next examples, the type TT we mentioned earlier, will be the Real Numbers (R\R).

  • C0C_0 is the function that will be matched, by Church Encoding, to the natural number 00. The result of C0(f,3)C_0(f,3) is 33. Why? Because we applied ff to 33 zero times overall, I.e., we didn’t apply ff at all, and therefore we stayed with the original value, 33. Generally speaking, the function C0C_0 returns its second parameter for any function ff and any type TT.
  • The result of C1(f,3)C_1(f,3) is f(3)=23=6f(3)=2*3=6.
  • The result of C2(f,3)C_2(f,3) is f(f(3))=f(23)=2(23)=12f(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 nn to its corresponding CnC_n HOF, as CEC_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 ChC_h. We know it represents some natural number hh, but we don't know which number hh is. Therefore, we will calculate Ch(f,x)C_h(f,x) for f(x)=x+1f(x)=x+1 as ff, and 00 as xx. ChC_h is going to apply x+1x+1 to 00, hh times overall, and therefore our result will be 1h=h1*h=h as a result!

The mapping works in both directions! 🥳

We will name a HOF that was returned by CEC_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 CDC_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: CE(n+m)=CE(n)+CE(m)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 CEC_E.
On the right side, we apply CEC_E to each number nn and mm separately, and then sum the results – the Church functions that represent nn and mm. 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 Cn+CmC_n+C_m should be the function Cn+mC_{n+m}, the Church function which takes two parameters, ff and xx, and returns ff applied to xx, n+mn+m times. Similarly, we will define the multiplication between Church functions: the result of CnCmC_n*C_m will be CnmC_{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 TT to a value from TT, and a value of TT. This TT can be any type, so TT is a generic parameter (or a type parameter) of this wrapped function. This is the way to write that in Haskell:

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 C0C_0, C1C_1 and C2C_2:

As we said earlier, C0C_0, or zero, doesn’t apply f to x at all, and returns the xx. C1C_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:

We used the function that the CNumber holds to apply (+1) – which corresponds to f(x)=x+1f(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 11), succ one returns two, and so on.

Given that succ receives a CNumber that represents nn, 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 nn times, and then apply f to the result once again. And so, we get the CNumber that represents n+1n+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.

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

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

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

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.

Again, we assume that a and b are Church functions that represents nn and mm, 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, nn times overall. As b is a Church function which represents mm, the total result will be a CNumber that holds a Church function which represents nmn*m.

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

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