church.ts

type ChurchInput<T> = (t: T) => T;
type ChurchNumeral<T> = (fn: ChurchInput<T>) => (t: T) => T;

function churchToInt(c: ChurchNumeral<number>) {
  return c((x: number) => x + 1)(0);
}

function ZERO<T>(f: any) {
  return (x: T) => x;
}
function ONE<T>(f: ChurchInput<T>) {
  return (x: T) => f(x);
}
function TWO<T>(f: ChurchInput<T>) {
  return (x: T) => f(f(x));
}

function increment<T>(n: ChurchNumeral<T>): ChurchNumeral<T> {
  return (f) => (x) => f(n(f)(x));
}
const THREE = increment(TWO);
const FOUR = increment(THREE);

function multiply<T>(
  n: ChurchNumeral<T>,
  m: ChurchNumeral<T>
): ChurchNumeral<T> {
  return (f) => (x) => m(n(f))(x);
}

function add<T>(n: ChurchNumeral<T>, m: ChurchNumeral<T>): ChurchNumeral<T> {
  return (f) => (x) => n(f)(m(f)(x));
}

function exp<T>(
  n: ChurchNumeral<T>,
  m: ChurchNumeral<ChurchInput<T>>
): ChurchNumeral<T> {
  return m(n);
}

type ChurchBoolean<T> = (t: T) => (f: T) => T;

function churchToBool(c: ChurchBoolean<boolean>) {
  return c(true)(false);
}
function TRUE<T>(x: T): (t: T) => T {
  return (y: T) => x;
}
const FALSE = ZERO;

type ChurchPair<T> = (s: ChurchBoolean<T>) => T;

function cons<T>(x: T): (y: T) => ChurchPair<T> {
  return (y: T) => (s: ChurchBoolean<T>) => s(x)(y);
}

function car<T>(p: ChurchPair<T>): T {
  return p(TRUE);
}
function cdr<T>(p: ChurchPair<T>): T {
  return p(FALSE);
}

function selfAndInc<T>(x: ChurchNumeral<T>): ChurchPair<ChurchNumeral<T>> {
  return cons(x)(increment(x));
}

function shift<T>(
  p: ChurchPair<ChurchNumeral<T>>
): ChurchPair<ChurchNumeral<T>> {
  return selfAndInc(cdr(p));
}

function decrement<T>(
  n: ChurchNumeral<ChurchPair<ChurchNumeral<T>>>
): ChurchNumeral<T> {
  return car(n(shift)(cons<ChurchNumeral<T>>(ZERO)(ZERO)));
}

function isZero<T>(n: ChurchNumeral<ChurchBoolean<T>>): ChurchBoolean<T> {
  return n(() => FALSE)(TRUE);
}

// Unfortunately, this is as far as I can get - AFAICT there is no way to type
// the eager y-combinator in typescript.