y-comibinator.js

// 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))

*/