10

Y コンビネータの考え方を数学的に理解していると思います。これは、与えられた汎関数の不動点を返すためF、 whereesf = Y(F)はfを満たしf == F(f)ます。

しかし、実際の計算プログラムがどのように機能するのかわかりませんか?

ここに示す JavaScript の例を見てみましょう。

var Y = (F) => ( x => F( y => x(x)(y) ) )( x => F( y => x(x)(y) ) )
var Factorial = (factorial) => (n => n == 0 ? 1 : n * factorial(n-1))

Y(Factorial)(6) == 720    // => true
computed_factorial = Y(Factorial)

私が理解していない部分は、computed_factorial関数 (固定小数点) が実際にどのように計算されるかです。Y の定義をたどると、その部分で無限再帰x(x)に遭遇することがわかります。そこで暗示されている終了ケースは見当たりません。しかし、それは奇妙なことに戻ってきます。誰でも説明できますか？

4

4 に答える 4

3

ES6 アロー関数構文を使用します。あなたは CoffeeScript を知っているようなので、問題なく読めるはずです。

これがYコンビネータです

var Y = F=> (x=> F (y=> x (x) (y))) (x=> F (y=> x (x) (y)))

私はあなたのfactorial機能の改良版を使用するつもりです。これは代わりにアキュムレータを使用して、評価が大きなピラミッドに変わるのを防ぎます。この関数のプロセスは線形反復ですが、あなたのプロセスは再帰的です。ES6が最終的にテールコールを排除すると、これはさらに大きな違いになります.

構文の違いはわずかです。Yがどのように評価されるかを確認したいだけなので、とにかく重要ではありません。

var factorial = Y (fact=> acc=> n=>
  n < 2 ? acc : fact (acc*n) (n-1)
) (1);

これにより、すでにコンピューターは何らかの作業を開始します。それでは、先に進む前にこれを評価しましょう...

テキスト エディターに本当に優れたブラケット ハイライターがあることを願っています...

var factorial
= Y (f=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (1)                                                                                                                                                                // sub Y
= (F=> (x=> F (y=> x (x) (y))) (x=> F (y=> x (x) (y)))) (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (1)                                                                                                         // apply F=> to fact=>
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (1)                                                               // apply x=> to x=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1) // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (1)             // apply acc=> to 1
= n=> n < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*n) (n-1)                             // return value
= [Function] (n=> ...)

呼び出した後、ここで確認できます。

var factorial = Y(fact=> acc=> n=> ...) (1);
//=> [Function] (n=> ...)

単一の入力を待っている関数が返されますn。階乗を実行してみましょう

先に進む前に、javascript repl にコピー/貼り付けすることで、ここにあるすべての行が正しいことを確認できます(確認する必要があります) 。各行が返されます (これが の正解です。ネタバレしてしまい申し訳ありません)。これは、分数を単純化したり、代数方程式を解いたり、化学式のバランスを取ったりするときと似ています。各ステップは正しい答えでなければなりません。24factorial(4)

私のコメントについては、必ず右端までスクロールしてください。各行でどの操作を完了したかを説明します。完了した操作の結果は次の行にあります。

そして、そのブラケット蛍光ペンが再び手元にあることを確認してください...

factorial (4)                                                                                                                                                                                                                     // sub factorial
= (n=> n < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*n) (n-1)) (4)                                 // apply n=> to 4
= 4 < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1)                                           // 4 < 2
= false ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1)                                           // ?:
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1)                                                       // 1*4
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (4-1)                                                         // 4-1
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (3)                                                           // apply y=> to 4
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (4) (3)                                                                     // apply x=> to x=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (3)       // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (4) (3)                   // apply acc=> to 4
= (n=> n < 2 ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*n) (n-1)) (3)                                 // apply n=> to 3
= 3 < 2 ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1)                                           // 3 < 2
= false ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1)                                           // ?:
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1)                                                       // 4*2
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (3-1)                                                        // 3-1
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (2)                                                          // apply y=> to 12
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (12) (2)                                                                    // apply x=> to y=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (2)      // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (12) (2)                  // apply acc=> 12
= (n=> n < 2 ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*n) (n-1)) (2)                               // apply n=> 2
= 2 < 2 ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1)                                         // 2 < 2
= false ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1)                                         // ?:
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1)                                                      // 12*2
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (2-1)                                                        // 2-1
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (1)                                                          // apply y=> to 24
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (24) (1)                                                                    // apply x=> to x=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (1)      // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (24) (1)                  // apply acc=> to 24
= (n=> n < 2 ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*n) (n-1)) (1)                               // apply n=> to 1
= 1 < 2 ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*1) (1-1)                                         // 1 < 2
= true ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*1) (1-1)                                          // ?:
= 24

の他の実装も見てきましYた。別のもの (javascript で使用するため) を最初から作成する簡単なプロセスを次に示します。

// text book
var Y = f=> f (Y (f))

// prevent immediate recursion (javascript is applicative order)
var Y = f=> f (x=> Y (f) (x))

// remove recursion using U combinator
var Y = U (h=> f=> f (x=> h (h) (f) (x)))

// given: U = f=> f (f)
var Y = (h=> f=> f (x=> h (h) (f) (x))) (h=> f=> f (x=> h (h) (f) (x)))
于 2016-05-29T06:35:06.407 に答える
2

遅延評価言語では、Y コンビネータは次のように定義できます。

Y = (f =>
  (x => f( x(x) ))
  (x => f( x(x) )))

しかし、Javascript は熱心な評価言語であるため、このようにYを定義すると、関数にYを適用しようとしたときにx(x)部分が無期限に再帰されます。

この問題を回避するために、匿名の「ラッパー」関数を導入してxの実行を遅らせることができます。このラッパー関数は、呼び出されるとx(x)と同じように動作しますが、単なる関数定義であるため、すぐに戻ります。

例の場合、 x(x)が再帰関数にバインドされることを知っています。

Factorial = f => n => n==0 ? 1 : n*f(n-1)

単一の引数のみが渡されることを前もって知ることができます。次のパターンを使用して、任意の関数f(x)と同じように動作する無名関数を生成できます。

f => x => f(x)

このパターンをx(x)項に適用すると、Yは無期限に再帰することはなくなり、次のようになります。

Y = (f =>
  (x => f( y => x(x)(y) ))
  (x => f( y => x(x)(y) )))
于 2016-05-29T08:22:56.520 に答える