# lambda calculus – 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)
``````

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? 