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.

Advertisements

~ by rebcabin on August 3, 2012.

3 Responses to “Shortening Y: version 3”

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

  2. 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

  3. 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 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: