functional-programming - Jan Willem Klop の "(LL L...)" Y コンビネータはどのように機能しますか?

Question

Y Combinator が何であるかは理解していますが、ウィキペディアのページからの「新しい」コンビネータのこの例は理解できません:

Yk = (LLLLLLLLLLLLLLLLLLLLLLLLLL)

どこ：

    L = λabcdefghijklmnopqstuvwxyzr. (r (thisisafixedpointcomb inator))

これはどのように作動しますか？

Answer 1

固定小数点コンビネータの本質は、CにC f還元されることf (C f)です。Cこれを行う限り、何を服用しても問題ありません。だから代わりに

(\y f. f (y y f)) (\y f. f (y y f))

あなたも取ることができます

(\y z f. f (y y y f)) (\y z f. f (y y y f)) (\y z f. f (y y y f))

基本的に、フォームの何かが必要です

C t1 t2 ... tN

ti = Cいくつかの場所iと

C = \x1 x2 .. xN f. f (xi u1 u2 ... xi ... u(N-1) f)

他の用語tjおよびujは、実際には「使用」されていません。Lクロップがこの形式を持っていることがわかります(ただし、彼はすべてtiがL2 番目xiの も他の であり得るという事実を利用していますxj)。