Как работает комбинатор Y "Ян Виллем Клоп" (L L L ...) "Y?

Question

Я понимаю , что такое Y Combinator , но я не понимаю этот пример "нового" комбинатора со страницы Википедии :

 Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L)

Where:

    L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))

Как это работает?

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 равны L, так что второй xi также может быть любым другим xj).