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
   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
Holtsville, New York

... in the town is $68,544, and the median income for a family is $71,784. Males have a median income of $50,361 versus $31,709 for females. The per capita income for the ...

 
 
 
This page was created in 29.2 ms