# Tried to derive the Z combinator and instead derived another

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?

## 1 Answer

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