# Church integer

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

$\mathrm{church}0$ | $=fx\to x$ | ||

$\mathrm{church}n$ | $=c$ | ||

$\mathrm{where}:cfx={c}^{\prime}f(fx)$ | |||

$\mathrm{where}:{c}^{\prime}=\mathrm{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$.

Title | Church integer |
---|---|

Canonical name | ChurchInteger |

Date of creation | 2013-03-22 12:32:31 |

Last modified on | 2013-03-22 12:32:31 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 8 |

Author | mathcam (2727) |

Entry type | Definition |

Classification | msc 03B40 |

Classification | msc 68N18 |

Related topic | LambdaCalculus |