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
Thomas a Kempis

... of Christ," was born at Kempen[?], Germany (40 miles northwest of Cologne) in 1380 and died near Zwolle (52 miles east-north-east of Amsterdam) in 1471. His paternal name ...

 
 
 
This page was created in 32.8 ms