14

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?

Community
  • 1
  • 1
raldi
  • 21,344
  • 33
  • 76
  • 86

1 Answers1

12

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

mweerden
  • 13,619
  • 5
  • 32
  • 32