Menu
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?
752
The Y combinator is a central concept in lambda calculus, which is the formal foundation of functional languages. Y allows one to define recursive functions without using self-referential definitions.
The Y combinator is a formula which lets you implement recursion in a situation where functions can't have names but can be passed around as arguments, used as return values, and defined within other functions. It works by passing the function to itself as an argument, so it can call itself.
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).
191
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
