Encyclopedia > Church integer

  Article Content

Church integer

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). 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
Michael Barrymore

...     Contents Michael Barrymore Michael Barrymore, born 4 May 1952, is a British comedian famous for his variety shows. This article is a ...

 
 
 
This page was created in 32.3 ms