Encyclopedia > Church numeral

  Article Content

Church integer

Redirected from Church numeral

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
     c f x = c' f (f x)
         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). This article is open-content.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... Demographics Main article: Demographics of Brazil Four major groups make up the Brazilian population: the Portuguese, the original colonisers; Africans brought to ...

This page was created in 23.7 ms