Combinators and recursion are always mind bending.
Joel Thoms
2

So here’s my finding (warning : this is math rather than javascript …) :

We want to define function f with a reference to itself. Said another way, we know a function G such that f = G(f).

Let’s consider functions h = g => G(U(g)), and k = U(h).

According to definition of U, k = h(h). According to definition of h applied to the outer h, k = G(U(h)). And according to definition of k, k = G(k).

If we assume unicity of f, we have f = k.

So we should define operator V = G => U(g => G(U(g))), and that way, in order to define f verifying f = G(f), we simply have f = V(G). We have transformed a recursive expression in a non-recursive one.

Example :

Lets assume this a standard case of recursion in javascript :

const fibonacci = n => n < 2 ? n : fibonacci(n — 1) + fibonacci(n — 2)

You would use the V operator for the exact same use case in the following way :

const fibonacci = V(fib => n => n < 2 ? n : fib(n — 1) + fib(n — 2)).

Which I find more readable than using the U operator directly. Here, I don’t have to remember to apply it twice to itself.

What do you think?

Edit : V is in actual fact the exact definition of the Y combinator.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.