Y Combinator
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
// utility range function, creates a list of [0, 1, 2, ..., i]
const range = i => [...Array(i).keys()]
// fixed point, Y combinator (proof at the end of the code)
const fix = f =>
(g => z => f(g(g))(z)) (g => z => f(g(g))(z))
// open recursive definition of factorial funciton
// note that x is a funciton
// h is full factorial function if x is full factorial function
// h(h(h(h(...)))) is the full factorial function
let h = x => n => n === 0 ? 1 : n * x(n - 1)
// utility function used later
let makeFi = (f, i) =>
i === 0 ? f(undefined) : f(makeFi(f, i-1))
// utility function used later
let makeFiName = (gname, g, i) => {
if(i === 0) {
return {name: `${gname}(undefined)`, f: g(undefined)}
} else {
let {name, f} = makeFiName(gname, g, i-1)
return {name: `${gname}(${name})`, f: g(f)}
}
}
// applying h in itself multiple times to converge to factorial
let h0 = h(undefined)
let h1 = h(h(undefined))
let h2 = h(h(h(undefined)))
console.log("h0(0) = ", h0(0))
console.log("h1(1) = ", h1(1))
console.log("h2(2) = ", h2(2))
console.log("...")
// makeFi utility is used to apply f five times on itself
const h5 = makeFi(h, 5)
console.log("h5(5) = ", h5(5))
console.log("-----")
// check the output
const fs = range(10).map(i => ({i: i, f: makeFiName('h', h, i)}))
const fit = ({name, f}, i) => j => {
const func = `h${i}(${j}) = ${name}(${j})`
try {
console.log(`${func} = ${f(j)}`)
fit({name, f}, i)(j + 1)
} catch (ex) {
console.log(`${func} = undefined`)
}
}
fs.forEach(({i, f}) => {
fit(f, i)(0)
console.log("-----")
})
// finally factorial is f(h) = h(fix(h)) = h(h(fix(h))) = h(h(h(fix(h)))) = ...
const fact = fix(h)
console.log("fact(10) = ", fact(10))
console.log("fact(100) = ", fact(100))
/*
proof: fix(h) = h(fix(h)) = h(h(fix(h))) == ...
fix = f =>
(g => z => f(g(g))(z)) (g => z => f(g(g))(z))
fix(h)
(f =>
(g => z => f(g(g))(z)) (g => z => f(g(g))(z))
)(h)
// apply h
(g => z => h(g(g))(z)) (g => z => h(g(g))(z))
z => h((g => z => h(g(g))(z))((g => z => h(g(g))(z))))(z)
// beta reduction
h((g => z => h(g(g))(z))((g => z => h(g(g))(z))))
// just look at it!
h((g => z => h(g(g))(z)) ((g => z => h(g(g))(z))))
h(fix(h))
*/
JavaScript
INFO