如何编写一个固定点为Y组合子的函数？

Question

我必须找到一个G具有固定点的函数,这个固定点必须是Y组合子.

回想一下Y F = F(Y F)所有人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在他的回答中所写)的固定点.

Answer 2

对于所有值v,该函数const v具有(唯一的,因此也是最小的)定点v.