Mar 14, 2016

Church numerals in ES6

Just because it’s fun to play with the natural numbers in wildly impractical ways.

Gist. Also pasted below.

/*jshint esversion: 6 */
'use strict';

// Church numerals in ES6.
// c.f. https://en.wikipedia.org/wiki/Church_encoding

// Zero is the identity function.
let zero = (f => x => x);

// Successor: apply function one more time.
let succ = (n => f => x => f(n(f)(x)));

let one = succ(zero);

// Convert a Church numeral into a concrete integer.
let plus1 = x => x + 1;
let church2int = n => n(plus1)(0);

// Convert a concrete integer into a church numeral.
function int2church(i) {
  if (i === 0) {
    return zero;
  } else {
    return succ(int2church(i - 1));
  }
}

// Add two Church numerals.
let add = m => n => f => x => n(f)(m(f)(x));

// Multiply two Church numerals.
let mult = m => n => f => x => n(m(f))(x);

// Exponentiation: n^m
let exp = m => n => n(m);

/////////////////// Some random operations.
console.log(church2int(int2church(10)));
console.log(church2int(zero));
console.log(church2int(one));

let c11 = int2church(11);
let c22 = int2church(22);
let plus_11_22 = add(c11)(c22);
console.log("11 + 22 = " + church2int(plus_11_22));

let mult_11_22 = mult(c11)(c22);
console.log("11 * 22 = " + church2int(mult_11_22));

let two = succ(one);
let ten = int2church(10);
let c_two_e_10 = exp(two)(ten);

console.log("2 ^^ 10 = " + church2int(c_two_e_10));