Y-Combinator

yCombinator.md

A Note from kestas.kuliukas.com rewritten using arrow function/const.

const fact = (n) => n === 1 ? 1 : n*fact(n-1)

1. factory fact function

const makeFact = givenFact => n => n === 1 ? 1 : n*givenFact(n-1)

Invariety: fact(n) === makeFact(givenFact)(n)

1. use makeFact to compute givenFact

const makeRealFact = (makeFact) => {
    const givenFact = (n) => {
        return makeFact(givenFact)(n)
    }
    return makeFact(givenFact)
}

Invariety: fact(n) === makeFact(givenFact)(n) === makeRealFact(makeFact)(n)

Note: makeRealFact is our Y function that uses makeFact to do the acutal factorial function.

Recursive calls: givenFact(n) => makeFact(givenFact)(n) => makeFact(makeFact(givenFact))(n) => ... makeFact(makeFact(makeFact ... ))(n)

Finally makeFact will eliminate givenFact since makeFact does not always call givenFact.

1. Now we need to eliminate the givenFact reference in givenFact, hence we use getNextGivenFact() to evaluate givenFact.

const makeRealFact = (makeFact) => {
    const getNextGivenFact = () => {
        const givenFact = (n) => {
            return makeFact(getNextGivenFact())(n)
        }
        return makeFact(givenFact)
    }
    return getNextGivenFact()
}

1. Now we need to eliminate the getNextGivenFact reference, hence we pass getNextGivenFact to itself as a parameter.

const makeRealFact = (makeFact) => {
    const getNextGivenFact = (getNextGivenFactRef) => {
        const givenFact = (n) => {
            return makeFact(getNextGivenFactRef(getNextGivenFactRef))(n)
        }
        return makeFact(givenFact)
    }
    return getNextGivenFact(getNextGivenFact)
}

1. Now that makeRealFact can compute fact recursively without using any variables, we will do the refactor to make it simple and human-comphrehensity-proof.

const makeRealFact = (makeFact) => {
    const getNextGivenFact = (getNextGivenFactRef) => makeFact(n => makeFact(getNextGivenFactRef(getNextGivenFactRef))(n))
    return getNextGivenFact(getNextGivenFact)
}

1. Now we use anonymous function to rewrite makeRealFact again:

const makeRealFact = (makeFact) => 
    ((getNextGivenFact) => getNextGivenFact(getNextGivenFact))
    ((getNextGivenFactRef) => makeFact(n => makeFact(getNextGivenFactRef(getNextGivenFactRef))(n)))

1. Now we use short initials to make even more obscure:

const Y = (f) => (x => x(x))(x => f(t => x(x)(t)))

where f = makeFact, x = getNextGivenFact(Ref), t = n.

The le might be short for lambda-terms \lambda E (see https://en.wikipedia.org/wiki/Combinatory_logic). The Y combinator can be expressed in lambda caculus as following

Y = λf.(λx.f (x x)) (λx.f (x x))