## Shortening Y: version 3

In an earlier post, we derived the Y combinator for converting self-parameterized functions into anonymous recursive functions. We suggested memorizing it, and, indeed, we can type it from memory, going over the derivation mentally:

(function (f) { return (function (h) { return f(function (n) { return h(h)(n);});}) (function (h) { return f(function (n) { return h(h)(n);});});})

and, testing it (F12 in the browser, find console, copy & paste):

(function (f) { return (function (h) { return f(function (n) { return h(h)(n);});}) (function (h) { return f(function (n) { return h(h)(n);});});}) (function (g) { return function (n) { return n<2 ? 1 : n*g(n-1);};})(13)

which yields 6227020800.

We notice that we’re repeating ourselves, and this isn’t a great idea.

We can polish the tool a little bit, and it will save us even more time and mental energy (that’s the whole point of using tools in the first place).

Applying a function to itself is just an application of a certain, trivial function:

function (g) {return g(g);}

So our Y must be

(function (f) { return (function (g) {return g(g);}) (function (h) { return f(function (n) { return h(h)(n);});});}) (function (g) { return function (n) { return n<2 ? 1 : n*g(n-1);};})(13)

just applied directly to its test function, factorial.

There is even more polishing we can do, for another time.

[…] far, our shortest version of the Y combinator is the […]

One Y for Any Number of Arguments: version 4 « The Light Cone (Brian's space-time) said this on August 3, 2012 at 2:18 pm |

Here is another derivation, this time in C#, from a different point of view (more bottom-up!)

http://blogs.msdn.com/b/wesdyer/archive/2007/02/02/anonymous-recursion-in-c.aspx

rebcabin said this on September 27, 2012 at 4:25 pm |

Wes’s derivation, linked above, takes all the mystery and magic and invocations of genius out of the derivation of the Y combinator. That is a good thing 🙂

rebcabin said this on September 28, 2012 at 1:36 pm |