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$ .