javascriptで、Yコンビネータ

メモ。
式変形など。わからないなりに。

Yコンビネータって？

再帰関数gが関数fによって次のように表現されるときを考えます。

g = f(g)

たとえば、フィボナチ数のときは、

f = function(fib){
    return function(n){
        return (n <= 2) ? 1
                        : fib(n - 1) + fib(n - 2);
    }
}

メモ化させるなら、

f = function(fib){
    var memo = {};
    return function(n){
        return memo[n] || (memo[n] =
            (n <= 2) ? 1
                     : fib(n - 1) + fib(n - 2));
    }
}

たとえば、階乗のときは、

f = function(fact){
    return function(n){
        return (n == 1) ? 1
                        : n * fact(n - 1);
    }
}

このとき、

g = Y(f)

となる関数YがYコンビネータ。関数fを引数にしたとき、再帰関数gを返す関数YをYコンビネータというようだ。
この関数Yは、

f(Y(f)) = Y(f)

をみたす。つまり、Y(f)にfをいくら作用させても変わらない。

f(f(f(f( ･･･ f(Y(f)) ･･･ )))) = Y(f)

このY(f)の不変性から、Yは不動点関数あるいは不動点演算子とも呼ばれるようだ。

もうすこし具体的に、Yって、どう表現できるの？

再帰関数gに引数を与えて計算すると

g(m) = f(g)(m)

だから、

g = function(m){
    return f(g)(m);
}

と書ける。これを、

Y(f) = g

に適用すると、

Y = function(f){
    var g = function(m){
        return f(g)(m);
    }
    return function(m){
        return f(g)(m);
    }
}

高階関数を導入して変数変換をすると、

Y = function(f){
    var h = function(k){
        return function(m){
            return f(k(k))(m);
        }
    }
    var g = h(h);
    return function(m){
        return f(h(h))(m);
    }
}

つまり、

Y = function(f){
    return (function(h){
        return function(m){
            return f(h(h))(m);
        }
    })(function(k){
        return function(m){
            return f(k(k))(m);
        }
    });
}

自由変数を一切使わず、引数の変数のみで表現している。そのため引数名を変えられる。

Y = function(f){
    return (function(g){
        return function(m){
            return f(g(g))(m);
        }
    })(function(g){
        return function(m){
            return f(g(g))(m);
        }
    });
}

上記は再帰関数が１つの引数をとるものと仮定した場合のjavascriptでの表現。
Yコンビネータの返す再帰関数が複数の引数をとりうると想定したjavascriptでの表現は次のようになる。

Y = function(f){
    return (function(g){
        return function(){
            return f(g(g)).apply(null, arguments);
        }
    })(function(g){
        return function(){
            return f(g(g)).apply(null, arguments);
        }
    });
}

途中で変数変換できるところがおもしろい。あの変数変換の仕方がほかにもあるのならYコンビネータの表現は複数あるということになるのかな。一意に決まるのかどうか正確な議論があったりするのかな。あの高階関数を利用した自己言及的な変数変換が再帰関数を返すことのできる根拠につながるのかな。初めの条件に再帰があるから当然といえるのかもしれないけれど。

それにしても不思議なかたちだ。