Y Combinator

Recently I've learning some JavaScript and of course I found the wonderful material by Douglas Crockford. Something that I found particularly interesting (just because he says is for enlightened people ;) is the Y Combinator and he even provides an implementation in JavaScript. Since I wanted to know more and thought it was a good challenge I started looking for some readings to understand it, I found it and I have to say that it is the most beautiful thing I have learned to date regarding programming, it is elegant, succint, expressive, powerful and fun.

Certainly it is not easy to understand, but a couple of hours are enough to have your own implementation, I found particularly useful and easy to understand this page that should be pretty easy to find in any search engine.

Below I am sharing with you what I found so before continue, I highly recommend you to get familiarized with it.

The Factorial

Let's begin with this simple function, remember that we want it to be anonymous:

var fStar = function(funcArg) {
    return function(n) {
        return n === 0 ? 1 : n * funcArg(n - 1);
    };
};
 
var fact = (
 function(procedure) { 
  return fStar(function(arg){ 
   return procedure(procedure)(arg) 
  }); 
 }
)(
 function(procedure) { 
  return fStar(function(arg) { 
   return procedure(procedure)(arg) 
  }); 
 }
);

Now let's build it through the Y Combinator:

var Y = function(X) {
 // Leave parenthesis as they are.
 return (
  function(procedure) { 
   return X(function(arg) { 
    return procedure(procedure)(arg);
   }); 
  }
 )(
  function(procedure) { 
   return X(function(arg) { 
    return procedure(procedure)(arg);
   }); 
  }
 );
};

Compare to Crockford's implementation which is more elegant:

function Y$(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

Now building factorial becomes pretty succint:

var otherFact = Y(fStar);

But that is not all, you can also build a function that finds the max in an array pretty easily:

var maxStar = function(funcArg) {
 return function(array) {
  if(array.length === 0) {
   throw "at least one element is required...";
  }
  
  if(array.length === 1) {
   return array[0];
  }
  
  var last = array.clone().pop();
  var otherMax = funcArg(array);
  return last > otherMax ? last : otherMax;
 };
};
 
var findMax = Y(maxStar);

OK I got it, lets have fun!

First be warned: I didn't find and easy and elegant way to do pattern matching in functional javascript and since is just an exercise for fun, please be tolerant with it.

Lets build some recursive functions found in Peano arithmethic:

The successor

var successor = function (n) {
    return n + 1;
};

The Sum!

var sumStar = function (funcArg) {
    return function (arg) {
        if (arg.n === 0) {
            return arg.m;
        }
 
        return successor(funcArg({ m: arg.m, n: arg.n - 1 }));
    };
};
 
var sum = Y(sumStar);

Multiplication

var multStar = function (funcArg) {
    return function (arg) {
        if (arg.n === 0) {
            return 0;
        }
 
        return sum({ m: funcArg({ m: arg.m, n: arg.n - 1 }), n: arg.m });
    };
};
 
var mult = Y(multStar);

Exponential

var expStar = function (funcArg) {
    return function (arg) {
        if (arg.power === 0) {
            return 1;
        }
 
        return mult({ m: funcArg({ base: arg.base, power: arg.power - 1 }), n: arg.base });
    };
};
 
var exponential = Y(expStar);

Conclusion

As you can see, this technique is very expressive and powerful, I've spent some years as a professional without knowing about its existence, but I am looking forward for places where this can be useful, and certainly I still need to make the switch to functional thinking that JavaScript as any other functional language provides.