Church numerals
This page is the answer to the task Church numerals in the Rosetta Code.
Contents
- 1 Description (from Rosetta Code)
- 2 Answers
- 2.1 Church numeral zero
- 2.2 The succesor function
- 2.3 Subsecuent Church numerals from the Church numeral zero and the succesor function
- 2.4 The sum function
- 2.5 The product function
- 2.6 The exponentiation function
- 2.7 Conversion from Church numerals to integers
- 2.8 Conversion from integers to Church numerals
- 2.9 Results as integers, operands given as Church numerals
- 2.10 Results as integers, operands converted from integers
Description (from Rosetta Code)
Task
In the Church encoding of natural numbers, the number N is encoded by a function that applies its first argument N times to its second argument.
- Church zero always returns the identity function, regardless of its first argument. In other words, the first argument is not applied to the second argument at all.
- Church one applies its first argument f just once to its second argument x, yielding f(x)
- Church two applies its first argument f twice to its second argument x, yielding f(f(x))
- and each successive Church numeral applies its first argument one additional time to its second argument, f(f(f(x))), f(f(f(f(x)))) ... The Church numeral 4, for example, returns a quadruple composition of the function supplied as its first argument.
Arithmetic operations on natural numbers can be similarly represented as functions on Church numerals.
In your language define:
- Church Zero,
- a Church successor function (a function on a Church numeral which returns the next Church numeral in the series),
- functions for Addition, Multiplication and Exponentiation over Church numerals,
- a function to convert integers to corresponding Church numerals,
- and a function to convert Church numerals to corresponding integers.
You should:
- Derive Church numerals three and four in terms of Church zero and a Church successor function.
- use Church numeral arithmetic to obtain the the sum and the product of Church 3 and Church 4,
- similarly obtain 4^3 and 3^4 in terms of Church numerals, using a Church numeral exponentiation function,
- convert each result back to an integer, and return it or print it to the console.
Answers
Church numeral zero
By definition:
The succesor function
The succesor function is defined as:
The orange mapping symbol is a lambda expression builder: It creates a lambda expression where its components (variables, body) are calculated from other expressions.
Subsecuent Church numerals from the Church numeral zero and the succesor function
The sum function
The sum function is defined as:
Example. Adding the numeral 3 and 4:
The product function
The product function is defined as:
Example. Multiplying the numeral 3 and 4:
The exponentiation function
The exponentiation function is defined as:
Example. Powering the numerals 4^{3} and 3^{4}:
Conversion from Church numerals to integers
It is achieved giving an incrementer as function, and a value of zero to a given Church numeral:
Example:
Conversion from integers to Church numerals
It is achieved calling recursively the succesor function from a Church numeral zero.
Example:
Results as integers, operands given as Church numerals
It calculates 3 + 4, 3 × 4, 4^{3} and 3^{4}:
Results as integers, operands converted from integers
It calculates 3 + 4, 3 × 4, 4^{3} and 3^{4}: