Skip to content

Instantly share code, notes, and snippets.

@takanuva
Created January 6, 2023 21:23
Show Gist options
  • Save takanuva/c94306509c6aecfa5a7c13c7e0a7ec49 to your computer and use it in GitHub Desktop.
Save takanuva/c94306509c6aecfa5a7c13c7e0a7ec49 to your computer and use it in GitHub Desktop.
Factorial and Fibonacci using Church-encoded numbers
// Can we write programs without control flow, variables, or even recursion?
// Well, of course we can! Church did that with pen and paper! :)
const to_num = (n) => n((x) => x + 1)(0)
const ZERO = (f) => (x) => x
const ONE = (f) => (x) => f(x)
const TWO = (f) => (x) => f(f(x))
const THREE = (f) => (x) => f(f(f(x)))
const FOUR = (f) => (x) => f(f(f(f(x))))
console.log(to_num(ZERO))
console.log(to_num(ONE))
console.log(to_num(FOUR))
const SUCC = (n) => (f) => (x) => f(n(f)(x))
const FIVE = SUCC(FOUR)
const SIX = SUCC(FIVE)
const SEVEN = SUCC(SIX)
const EIGHT = SUCC(SEVEN)
console.log(to_num(EIGHT))
const PLUS = (n) => (m) => (f) => (x) =>
n(f)(m(f)(x))
console.log(to_num(PLUS(EIGHT)(FIVE)))
const MULT = (n) => (m) => (f) => (x) =>
n(m(f))(x)
console.log(to_num(MULT(EIGHT)(FIVE)))
const PRED = (n) => (f) => (x) =>
n((g) => (h) => h(g(f)))((u) => x) ((u) => u)
console.log(to_num(PRED(MULT(EIGHT)(FIVE))))
const MINUS = (n) => (m) =>
m(PRED)(n)
console.log(to_num(MINUS(EIGHT)(FIVE)))
const PAIR = (a) => (b) => (f) =>
f(a)(b)
const FIRST = (p) =>
p((a) => (b) => a)
const SECOND = (p) =>
p((a) => (b) => b)
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
const FIB = (n) =>
// Corecursion
FIRST(
// Step
n(p =>
PAIR(SECOND(p))(PLUS(FIRST(p))(SECOND(p)))
// Seed
)(PAIR(ZERO)(ONE)))
console.log(to_num(FIB(EIGHT)))
// 1, 1, 2, 6, 24, 120, ...
const FAT = (n) =>
// Corecursion again
SECOND(
// Step
n(p =>
PAIR(SUCC(FIRST(p)))( MULT(FIRST(p))(SECOND(p)))
// Seed
)(PAIR(ONE)(ONE)))
console.log(to_num(FAT(FIVE)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment