haskell - 如何编写一个以Y组合子为不动点的函数？

Question

我必须找到一个有固定点的函数G，并且这个固定点必须是Y组合器。

回想一下，对于所有F，Y F = F(Y F)。我想要一个函数 G 使得 G Y = Y。

如何在 Haskell 中编写这样的函数？

Answer 1

让

g w = \f -> f (w f)

那么，如果

y f = f (y f)

我们有

g y
-- definition of g
= \f -> f (y f)
-- property of y
= \f -> y f
-- eta-conversion
= y

因此，y是g的不动点。

更重要的是:g 的定点集合正是定点组合子的集合。这是因为上面我们没有利用 y 的定义，而只是利用它是一个定点组合器这一事实。

注意，y也是id的定点(任何东西都是id的定点)和 const y (正如@DanielWagner 在他的回答中所写)。