CODEWITHSUNDEEP
functional-programminglispcomputer-science
raldi
raldi

Reputation: 22160

How does Jan Willem Klop's "(L L L...)" Y combinator work?

I understand what a Y Combinator is, but I don't understand this example of a "novel" combinator, from the 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))

How does this work?

Upvotes: 14

Views: 1261

Answers (1)

mweerden
mweerden

Reputation: 14051

The essence of a fixed-point combinator C is that C f reduces to f (C f). It doesn't matter what you take for C as long as does this. So instead of

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

you can just as well take

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

Basically you need something of the form

C t1 t2 ... tN

where ti = C for some i and

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

The other terms tj and uj are not actually "used". You can see that Klop's L has this form (although he uses the fact that all ti are L such that the second xi can also be any other xj).

Upvotes: 12

Related Questions