Baking the Y Combinator from Scratch

Is there a technique to remember this? I will understand it today and forget after a few weeks.

Yes.

Lambda calculus is about template substitution. It is the abstract mathematics of substituting templates into other templates. Alonzo Church got interested in this when he realized that it had numbers,

    type NumF = <X>(f: (x: X) => X) => (x: X) => X
    const zero: NumF = f => x => x
    const one: NumF = f => x => f(x)
    const two: NumF = f => x => f(f(x))

Addition is not too hard to define, multiplication is actually just function composition, and decrement is an unexpected motherf$@&er. To understand this last point, it may help to understand that this encoding of numbers is basically zero as [], one as [null], two as [null, null], etc and you are trying to use Array.prototype.reduce to compute the array with one fewer element. So you can do it with a (last, curr) pair or a null initial value, you have to know what those look like in the lambda calculus to translate,

    // predecessor and successor
    const succ = n => f => x => n(f(x))
    // Maybe fns: in λ-calc you'd uncurry
    type MaybeF<x> = <z>(ifNil: z, ifJust: (x: x) => z) => z
    const nil: MaybeF<any> = (ifNil, _ifJust) => ifNil
    function just<x>(x: x): MaybeF<x> {
      return (_ifNil, ifJust) => ifJust(x);
    }

    const pred = n =>
        n(maybe_n => maybe_n(just(zero), k => just(succ(k))))(nil)
      

Now you asked for a technique to remember the Y combinator. The basic thing to remember is the infinite template substitution discovered by Haskell Curry,

    (f => f(f))(f => f(f))

Forgetting everything you know about programming languages, and just thinking about template substitution, this is a template on the left, being substituted with a value on the right, and the reason it's an infinite loop is that after the substitution you get the exact same expression that you had before the substitution. [On the right we could have also written g => g(g) if that helps, the two variables are defined in separate scopes and only happen to have the same name f to make it clearer that this will loop infinitely if you try to eagerly evaluate it.]

Terms like this, were why Curry wanted a type theory. He immediately understood that this was kind of a weird expression because if you tried to express the idea of f(f) it was secretly holding on to a sort of paradox of self-reference or an infinity or whatever you want to call it. It is a function type which takes only the same function type as an argument, and returns God-knows-what. If you just forbid self-reference in the typing judgments, you don't get this sort of weird f(f) pathology.

So if you are remembering f(f) being somehow the key to the Y combinator, then you immediately see that you can kind of step it by not immediately evaluating it,

    const Q = (f => () => f(f))(f => () => f(f))

so as a matter of algebra Q() = Q although a programming language struggles to prove equality between functions so as a matter of programming that might not be equal. So this is a function you can call Q()()()() and it's just infinitely callable without producing any other values.

But why () =>, why not x => ? Well, you can introduce that but Q will just ignore it, it doesn't know what to do with that. So you need to write f(f)(x) to plumb it through to do something.

Note briefly that there IS a difference between f(f) and x => f(f)(x). The latter delays execution of f(f) until needed and so is still stepped, the former is an infinite loop.

And the last thing is that you need to hand this internal function to someone else, some decider, to decide when to call the recursion. This leads to the full form,

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

Usage with an example decider:

    const factorial = Y(recurse => n => n <= 1 ? 1 : n * recurse(n - 1));