functional-programming - Jan Willem Klop 的 "(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 的 L 具有这种形式(尽管他使用了所有 ti 都是 L 的事实，这样第二个 xi 也可以是任何其他 xj)。