Yコンビネータとメモ化の分離

よく読み返したら、k.inabaさんは僕が昨日やったのと同等のことをとっくになさっておられた。ので、まだinabaさんもなさっていないと思しきネタで捲土重来を期してみる。あ、言語は、見ての通り、昨日と同じくJavaScriptです。

// いわゆる普通のYコンビネータ
function Y(f) {
  function z(x) {
    return f(function(){
      return x(x).apply(this, arguments);
    });
  }
  return f(z(z));
}

// Yコンビネータにかける関数のための汎用メモ化関数
function memorize(f) {
  var memo = {};
  return function(x){
    return function(){
      var argHash = Array.prototype.join.call(arguments, ',');
      return memo[argHash] ||
            (memo[argHash] = f(x).apply(this, arguments));
    };
  };
}

// 例はフィボナッチ数列で
function fibonacci_gen(f){
  return function(n) {
    return (n<=2) ? 1 : f(n-1)+f(n-2);
  }
}
alert(Y(memorize(fibonacci_gen))(50));