PlanetMath: Church integer

(more info)

Math for the people, by the people.

donor list - find out how

Main Menu

Church integer

(Definition)

A Church integer is a representation of integers as functions, invented by Alonzo Church. An integer $N$ is represented as a higher-order function, which applies a given function to a given expression $N$ times.

For example, in the programming language Haskell, a function that returns a particular Church integer might be

$\displaystyle \operatorname{church} 0$	$\displaystyle = \ f x \rightarrow x$
$\displaystyle \operatorname{church} n$	$\displaystyle = c$
	$\displaystyle \operatorname{where}: c f x = c' f (f x)$
	$\displaystyle \hspace{.5in}\operatorname{where}: c' = \operatorname{church} (n - 1)$

The transformation from a Church integer to an integer might be

unchurch n = n (+1) 0

Thus we can generate the integers-the (+1) function would be applied to an initial value of $0$ $n$ times, yielding the ordinary integer $n$ .

"Church integer" is owned by mathcam. [ full author list (2) | owner history (1) ]

(view preamble | get metadata)

Log in to rate this entry.
(view current ratings)

Cross-references: generate, transformation, Haskell, language, expression, higher-order function, functions, integers, representation
There is 1 reference to this entry.

This is version 5 of Church integer, born on 2002-03-09, modified 2004-09-18.
Object id is 2785, canonical name is ChurchInteger.
Accessed 4479 times total.

Classification:

AMS MSC:	03B40 (Mathematical logic and foundations :: General logic :: Combinatory logic and lambda-calculus)
	68N18 (Computer science :: Software :: Functional programming and lambda calculus)

Pending Errata and Addenda

None.[ View all 3 ]

Discussion

forum policy

No messages.

Interact