functional programming - traduccion - ¿Cómo funciona Jan Willem Klop "(LL L...)" Y combinador?

lisp traduccion

Question

Entiendo lo que es un Y Combinator , pero no entiendo este ejemplo de un combinador "novedoso", de la página de Wikipedia :

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))

¿Como funciona esto?

Answer 1

La esencia de un combinador de punto fijo C es que C f reduce a f (C f) . No importa lo que tome para C , siempre y cuando lo haga. Entonces, en lugar de

(/y f. f (y y f)) (/y f. f (y y f))

también puedes tomar

(/y z f. f (y y y f)) (/y z f. f (y y y f)) (/y z f. f (y y y f))

Básicamente, necesitas algo de la forma

C t1 t2 ... tN

donde ti = C para algunos i y

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

Los otros términos tj y uj no son realmente "usados". Puedes ver que el L de Klop tiene esta forma (aunque usa el hecho de que todos los ti son L manera que el segundo xi también puede ser cualquier otro xj ).