2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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)))
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.