Church numerals

From Fōrmulæ wiki
Jump to: navigation, search

This page is the answer to the task Church numerals in the Rosetta Code.

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:

ChurchNumerals1.png


The succesor function

The succesor function is defined as:

ChurchNumerals2.png

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

ChurchNumerals3.png


The sum function

The sum function is defined as:

ChurchNumerals4.png

Example. Adding the numeral 3 and 4:

ChurchNumerals5.png


The product function

The product function is defined as:

ChurchNumerals6.png

Example. Multiplying the numeral 3 and 4:

ChurchNumerals7.png


The exponentiation function

The exponentiation function is defined as:

ChurchNumerals8.png

Example. Powering the numerals 43 and 34:

ChurchNumerals9.png


Conversion from Church numerals to integers

It is achieved giving an incrementer as function, and a value of zero to a given Church numeral:

ChurchNumerals10.png

Example:

ChurchNumerals11.png


Conversion from integers to Church numerals

It is achieved calling recursively the succesor function from a Church numeral zero.

ChurchNumerals12.png

Example:

ChurchNumerals13.png


Results as integers, operands given as Church numerals

It calculates 3 + 4, 3 × 4, 43 and 34:

ChurchNumerals14.png


Results as integers, operands converted from integers

It calculates 3 + 4, 3 × 4, 43 and 34:

ChurchNumerals15.png