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

Question

Я понимаю what a Y Combinator is, но я не понимаю, этот пример «нового» комбинатора, из Wikipedia page:

 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 фактически не используются. Вы можете видеть, что Klop's L имеет эту форму (хотя он использует тот факт, что все ti являются L, так что второй xi также может быть любым другим xj).