Kevin Lanni therealklanni

The Mysterious Y-Combinator

You may have heard the term before—you may even know what it is already. If you want a really technical description of the Y-combinator, look no further than Wikipedia (though we can certainly do better). However, this will leave most of us laymen more confused than we were going in. So what is the Y-combinator, really?

Getting right to it, written in ES6 this would look like the following (courtesy Brendan Eich):

let Y = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))

	const Yfact = Y(g => n => n <= 1 ? n : n * g(n - 1))

	// expanded as
	const Yfact = Y(g => {
	return n => {
	return n <= 1 ? n : n * g(n - 1)
	}
	})

	const fact = n => n <= 1 ? n : n * fact(n - 1)

	// expanded as
	const fact = n => {
	return n <= 1 ? n : n * fact(n - 1)
	}

	// original
	const Y = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))

	// expanded as
	const Y = f => {
	// return the result of this IIFE
	// f produces the fixed point function
	return (x => {
	// outer:
	f(v => {

	// pronounce Yl like "while" ;)
	let Yl = Y(f => (g, i) => {
	let r = g(i - 1)
	return r !== false ? r : f(g, i - 1)
	})

	// extremely contrived example using Yl

	let people = [ 'Shannon', 'Joseph', 'Eric', 'Mike']

	let Ym = (f, s = JSON.stringify) => (g => g(g))(x => f((...v) => (k => k in x ? x[k] : x[k] = x(x)(...v))(s(v))))

	let fib = Ym(f => n => n <= 1 ? n : f(n - 1) + f(n - 2))

	console.log('fib(1000)', fib(1000)) // => 4.346655768693743e+208

	const Y = f => {
	return (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))
	// --------------------------^
	}

	const Y = Yfact => {
	return (x => Yfact(v => x(x)(v)))(x => Yfact(v => x(x)(v)))
	}

	const Yfact = Y(inner => n => n <= 1 ? n : n * inner(n - 1))

	console.log(Yfact)
	// n => n <= 1 ? n : n * inner(n - 1)