16

Yコンビネータが理解できなかったので、ネイティブ実装なしで再帰を可能にする関数を実装してみました。いろいろ考えた結果、以下のようになりました。

Y = λx.(λv.(x x) v)

これは実際のものよりも短いです:

Y = λf.(λx.f (x x)) (λx.f (x x))

そして、驚いたことに、うまくいきました。いくつかの例：

// JavaScript
Y = function(x){
  return function(v){
    return x(x, v);
  };
};
sum = Y(function(f, n){
  return n == 0 ? 0 : n + f(f, n - 1);
});
sum(4);

; Scheme
(define Y (lambda (x) (lambda (v) (x x v))))
(define sum (Y 
    (lambda (f n) 
        (if (equal? n 0) 
            0 
            (+ n (f f (- n 1)))))))
(sum 4)

両方のスニペットは、期待どおり 10 (0 から 4 までの合計) を出力します。

これは何ですか、なぜ短いのか、なぜ長いバージョンが好まれるのでしょうか?

4

2 に答える 2

13

短い理由は、実装したものがY コンビネータではないためです。これは、実際の Y コンビネータと、U コンビネータとして知られることもあるものの中間にあるものです。適切な Y コンビネータになるには、次のように動作する必要があります。

(define sum
  (Y (lambda (f)
       (lambda (v) (if (equal? n 0) 0 (+ n (f (- n 1))))))))

またはJavascriptで：

sum = Y( function(f) { return function(n) {
  return n == 0 ? 0 : n + f(n-1);
};});

それを機能させる何かに取り組むと、それを長くする1つのことは、複製されたものをYに移動する必要があることがわかります.f次にそれをさらに長くするのは、終了するときです.x xこれらの言語は厳密であるため、関数内の自己適用を保護します。

于 2012-12-07T08:25:40.880 に答える
6

「実際の」バージョンとの違いは、通常は必要のないパラメーターとともに独自の関数を渡す必要があることです.Yは、関数にそれ自体の再帰バリアントを与えることでそれを抽象化します.

JavaScript の合計はちょうどいいはずです

Y (function(rec){ return function (n) { return n==0 ? 0 : n + rec(n-1); };})

よくあるJS式を

function Y (f) {
    function alt (x) {
        function rec (y) { // this function is basically equal to Y (f)
             return x(x)(y); // as x === alt
        }
        return f (rec);
    }
    return alt(alt);
}
于 2012-12-07T08:33:59.927 に答える