Church integer

You are here: irt.org | FOLDOC | Church integer

<theory> A representation of integers as functions invented by Alonzo Church, inventor of lambda-calculus. The integer N is represented as a higher-order function which applies a given function N times to a given expression. In the pure lambda-calculus there are no constants but numbers can be represented by Church integers.

A Haskell function to return a given Church integer could be written:

	church n = c
		   where
		   c f x = if n == 0 then x else c' f (f x)
			   where
			   c' = church (n-1)

A function to turn a Church integer into an ordinary integer:

	unchurch c = c (+1) 0