Y Combinator

Run Settings
LanguageJavaScript
Language Version
Run Command
// 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)) */
Editor Settings
Theme
Key bindings
Full width
Lines