A Church integer is a representation of natural numbers as functions, invented by Alonzo Church as part of his lambda calculus. The natural number n is represented as a higher-order function, which takes a function f as argument and returns the n-fold composition f o f o ... o f as result.
For example, in Haskell, a function that returns a particular Church integer might be
church 0 = \ f x -> x
church n = c
where
c f x = c' f (f x)
where
c' = church (n - 1)
The transformation from a Church integer to an integer might be
unchurch n = n (+1) 0
Thus the (+1) function would be applied to an initial value of 0 n times, yielding the ordinary integer n.
See lambda calculus for another expression of the same idea.
An earlier version of the above article was posted on PlanetMath (http://planetmath.org/encyclopedia/ChurchInteger.html). This article is open-content.
