関数だけでフィボナッチ数を求めてみる

JavaScriptの関数だけで

JavaScriptの関数を使って、フィボナッチ数を求めてみたいと思います。前回の「関数だけで四則演算をやってみた (後編)」の続きですので、Plus関数などのコードなどは前回を参照にしてください。

定数関数

まずは、どんな値を入力しても、同じ値を返す定数関数 Constを作ってみます。

var Const = function(x) {
  return function(y) {
    return x;
  };
};

たとえば、

var A = Const(2)

だと、A(2)も、A(3)も、A("hoge")も、すべて、2を返します。

フィボナッチ数の計算

さて、前前回で作ったチャーチ数と、和のPlus関数と、Const関数を使って、次のようなFibonacci関数を作ります。この関数を使って、フィボナッチ数を求めたいと思います。

var Fibonacci = function (n) {
  return n (
    function (f) {
      return function (a) {
        return function (b) {
          return f(b) (
            Plus(a)(b)
          )
        };
      };
    }
  ) ( Const )(_0)(_1);
};

使い方の例

先ほどのFibonacci関数を使って、0から5番目までの、項の数値を求めてみましょう。
なお、Successor関数と、ToNumber関数は、前前回を参照にしてください。

var _0 = function (f) {
           return function (x) {
             return x;
           };
         },
    _1 = function(f) {
           return function(x) {
             return f(x);
           };
         },
    _2 = function(f) {
           return function(x) {
             return f(f(x));
           };
         },
    _3 = Successor(_2),
    _4 = Successor(_3),
    _5 = Successor(_4);

ToNumber(Fibonacci(_0));  //0
ToNumber(Fibonacci(_1));  //1
ToNumber(Fibonacci(_2));  //1
ToNumber(Fibonacci(_3));  //2
ToNumber(Fibonacci(_4));  //3
ToNumber(Fibonacci(_5));  //5

前の2項の和になっているようです。

あとがき

今回は、よく知られている再帰関数や、for文やwhile文など、繰り返し文を使わない方法で、フィボナッチ数を求める関数を実装しました。
あと、コードについては、すべて、http://jwodder.freeshell.org/lambda.htmlのメモを参照しています。