Tried to derive the Z combinator and instead derived another

Question

I was working to derive the Z-Combinator by starting with the factorial function and ended up deriving a different fixed-point combinator. What did I derive? Did I make a subtle mistake?

Here are the steps I performed (in JavaScript)

1. Declare factorial function

let fact = n =>
    n < 2 ? 1 : n * fact(n - 1)

2. Convert to combinator (closed expression)

let fact = (self, n) =>
    n < 2 ? 1 : n * self(n - 1)

3. Thread self call

Based on signature fact(?, 7), passing fact as first argument seems reasonable fact(fact,7). So thread the parameter through the tail call:

let fact = (self, n) =>
    n < 2 ? 1 : n * self(self, n - 1)

Usage is now fact(fact,7) → 5040

4. Refactor to curried form

let fact = self =>
    n => n < 2 ? 1 : n * self(self)(n - 1)

5. Move self application to local declaration

let fact = self => {
    let f = n => self(self)(n)
    return n => n < 2 ? 1 : n * f(n - 1)
}

6. Convert let declaration to lambda expression

let fact = self =>
    (f =>
        n => n < 2 ? 1 : n * f(n - 1)
    )(
        n => self(self)(n)
    )

Usage is still fact(fact)(7) → 5040

7. Separate the factorial expression

let _fact = f => n =>
    n < 2 ? 1 : n * f(n - 1)

let fact = self =>
    (
        _fact
    )(
        n => self(self)(n)
    )

8. Move self-application from caller to body

let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact = (() => {
    let innerFact = self =>
        (
            _fact
        )(
            n => self(self)(n)
        )
    return innerFact(innerFact)
})()

Usage is now fact(7) → 5040

9. Convert let declaration to lambda expression

let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact = (() => {
    return (
        innerFact => innerFact(innerFact)
    )(
        self => (_fact)(n => self(self)(n))
    )
})()

10. Simplify expression

let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact =
    (innerFact => innerFact(innerFact))
    (self => (_fact)(n => self(self)(n)))

Sanity check. Usage is still fact(7) → 5040

11. Rename variables

The usage of innerFact and self look suspiciously similar. Rename to the same variable to discover a pattern. Separate lexical scopes so safe to do:

let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact =
    (u => u(u))
    (u => (_fact)(n => u(u)(n)))

12. Abstract _fact usage and rename fact

Rename fact to setup and abstract _fact in body by replacing with parameter f

let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

let fact = setup(_fact)

No need for separate _fact declaration so inline:

let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

let fact = setup(
    f => n => n < 2 ? 1 : n * f(n - 1)
)

13. Rename setup

Rename it to what? What combinator is this? According to Wikipedia The Z combinator is:

let Z = f => 
    (u => f(v => u(u)(v)))
    (u => f(v => u(u)(v)))

But what I've derived is:

let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

Defining fact in terms of either seems equivalent in behavior. Did I make a mistake? Did I accidentally rediscover another well-known combinator?

Answer 1

If I inline (u => (f)(n => u(u)(n))) into (u => u(u)) I get:

(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))

Which is exactly the Z-Combinator.

From wikipedia:

let Z = f => 
    (u => f(v => u(u)(v)))
    (u => f(v => u(u)(v)))

My derivation:

let fix = f =>
    (u => f(n => u(u)(n)))
    (u => f(n => u(u)(n)))