Instead of reverse engineering Crockford's Y, perhaps it's better to understand Y beginning with its purpose first. It's when we start with an intention and work our way forward to a solution that we can begin to understand how Y works.
"I want to write a recursive formula... without using recursion"
This was a problem facing mathematicians and logicians long before people had widespread access to computers. And this is the problem the Y combinator solves, but how does it do it? Let's first start with a recursive "formula" we want to write -
const fact = n =>
n <= 2
? n
: n * fact (n - 1) // <-- recursive!
Above fact is defined in terms of itself. We can remove this self-reference by using an extra parameter to control recursion, recur -
const fact = n =>
const fact = recur => n =>
n <= 2
? n
: n * fact (n - 1)
: n * ... (n - 1)
But what should recur be? And how do we fill in ...? Meet U. U simply applies a function to itself -
const U = f =>
f (f) // <-- apply f to itself
const fact = recur => n =>
n <= 2
? n
: n * U (recur) (n - 1) // <-- apply recur to itself
console.log (U (fact) (5)) // <-- apply fact to itself
// 120
Above we call U (fact) (5) to compute the result. It's important to observe that we could've applied U when we defined fact = ... -
const U = f =>
f (f)
const fact = U (recur => n => // <-- apply U directly on lambda
n <= 2
? n
: n * U (recur) (n - 1))
console.log (fact (5)) // <-- call fact normally
// 120
Using U, we now have a generic way to write recursive expressions -
U (recur => ... U (recur) ...)
"I don't like that I have to remember to use U (recur) (...). Can I just call recur (...) instead?"
U is an extremely simple mechanism, but indeed it is a little cumbersome because we have to remember to "reflect" recur back onto itself each time we recur. And this is where the Y combinator differs from the U. Y says,
- Give me function
f, that's asking for a recursion mechanism
- I'll give you a recursion mechanism,
x => ..., and when you call it, I will handle passing x to some U (recur) (...)
const Y = f =>
f (x => ...) // <-- instead of f (f)...
Just like we saw with fact above, we can write a recursive expression using U -
U (recur => ... U (recur) ...)
So Y of some function f, will create a recursion mechanism, U (recur => ...) and it will call f with a function, x => ..., that when applied, will recur with x using U (recur) (x) -
const Y = f =>
// f (x => ... (x))
// ======= ====
// | |
// v v
// U (recur => ... U (recur) ...)
U (recur => f (x => U (recur) (x)))
Let's see Y in action below -
const U = f =>
f (f)
const Y = f =>
U (recur => f (x => U (recur) (x)))
const fact = Y (recur => n =>
n <= 2
? n
: n * recur (n - 1)) // <-- call "recur" normally
console.log (fact (5)) // <-- call "fact" normally
// 120
tomato, tomahto
Crockford calls the Y-combinator "...one of the most strange and wonderful artifacts of Computer Science", but I think that's because he doesn't understand it and continues to copy/paste the same Y examples you see around the internet. There's nothing strange about it unless you write it in such a way that obfuscates all meaning -
// replace IIFE with U
function Y(le) {
return (
function (f) { return f(f); }
U
(function (f) {
return le(function (x) {
return f(f)(x);
return U(f)(x)
});
})
)
}
// remove unnecessary outer (...)
function Y(le) {
return U(function (f) {
return le(function (x) {
return U(f)(x)
})
})
}
// simplified arrow expression
const Y = le =>
U (f => le (x => U (f) (x))
// alpha rename "f" to "recur"
const Y = le =>
U (recur => le (x => U (recur) (x))
// alpha rename "le" to "f"
const Y = f =>
U (recur => f (x => U (recur) (x))
Which matches our version of Y above -
const Y = f =>
U (recur => f (x => U (recur) (x)))
without U
We can expand U such that Y has a standalone definition -
// starting with
const Y = f =>
U (recur => f (x => U (recur) (x)))
// expand inner U
const Y = f =>
U (recur => f (x => recur (recur) (x)))
// expand outer U
const Y = f =>
(recur => f (x => recur (recur) (x)))
(recur => f (x => recur (recur) (x)))
We're back to an IIFE, but this time our definition more closely matches Haskell Curry's original definition -
const Y = f =>
(recur => f (x => recur (recur) (x)))
(recur => f (x => recur (recur) (x)))
const fact = Y (recur => n =>
n <= 2
? n
: n * recur (n - 1))
console.log (fact (5))
// 120
expanding our Y intuition
Like almost all other Y tutorials out there, Crockford demonstrates using Y on a function with a single argument. There's a lot of potential lurking just beyond these preliminary understandings of Y. I'll show you simple functions that take 2 or even 3 arguments -
const Y = f =>
(recur => f (x => recur (recur) (x)))
(recur => f (x => recur (recur) (x)))
const range1 = Y (recur => m => n =>
m > n
? []
: [ m, ...recur (m + 1) (n) ])
const range2 = Y (recur => r => m => n =>
m > n
? r
: recur ([ ...r, m ]) (m + 1) (n)) ([])
const fib = Y (recur => a => b => n =>
n === 0
? a
: recur (b) (a + b) (n - 1)) (0) (1)
console.log (range1 (5) (10))
// [ 5, 6, 7, 8, 9, 10 ]
console.log (range2 (5) (10))
// [ 5, 6, 7, 8, 9, 10 ]
console.log (fib (10))
// 55
There's really no limit to the complexity of program that Y can express -
const Y = f =>
(recur => f (x => recur (recur) (x)))
(recur => f (x => recur (recur) (x)))
const reduce = Y (recur => i => f => state => a =>
i >= a.length
? state
: recur (i + 1) (f) (f (state, a[i])) (a)) (0)
const filter = f =>
reduce ((r, x) => f (x) ? [ ...r, x ] : r) ([])
const odds =
filter (n => n & 1)
console.log (odds ([ 0, 1, 2, 3, 4, 5, 6 ]))
// [ 1, 3, 5 ]
