Free On-line Dictionary of Computing:
church integer
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)