# Church integer

A Church integer is a representation of integers as functions, invented by Alonzo Church. An integer $N$ is represented as a higher-order function, which applies a given function to a given expression $N$ times.

For example, in the programming language Haskell, a function that returns a particular Church integer might be

 $\displaystyle\operatorname{church}0$ $\displaystyle=\ fx\rightarrow x$ $\displaystyle\operatorname{church}n$ $\displaystyle=c$ $\displaystyle\operatorname{where}:cfx=c^{\prime}f(fx)$ $\displaystyle \operatorname{where}:c^{\prime}=\operatorname{church}(% n-1)$

The transformation from a Church integer to an integer might be

unchurch n = n (+1) 0


Thus we can generate the integers–the (+1) function would be applied to an initial value of $0$ $n$ times, yielding the ordinary integer $n$.

Title Church integer ChurchInteger 2013-03-22 12:32:31 2013-03-22 12:32:31 mathcam (2727) mathcam (2727) 8 mathcam (2727) Definition msc 03B40 msc 68N18 LambdaCalculus