church integer

1 definition found

church integer - Free On-line Dictionary of Computing (26 May 2007) :

  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
  
     See also von Neumann integer.
  
     (1994-11-29)