haskell - 如何使用Y-组合器；为什么此无限递归返回9？

Y-组合器

我一直在尝试学习Y组合器(对此也很可爱)，并从wiki中得到了一个例子。在Haskell或Python中，对此主题的深入解释将不胜感激。高兴!

代码

fix :: (a -> a) -> a
fix f = f (fix f)

问题

当将fix应用于9时，称为fix的函数返回(\x -> 9)，但我不知道为什么。当我遵循堆栈时，我可以看到f(f ... (fix f) ...)。

>> fix (\x -> 9)
>> 9

最佳答案

首先:fix函数是使用直接递归实现的定点组合器。 Y组合器是一种特殊的定点组合器，不需要语法递归，因此它实现了与fix相同的功能，但方式不同。

如果您好奇，可以在SO上查看how to implement the Y combinator in Haskell。静态类型有点棘手-它需要递归类型才能工作。

至于第二个问题，由于懒惰，代码可以工作。如果将(\ x -> 9)应用于任何事物，则该事物将永远不会得到评估。试试这个:

λ> (\ x -> 9) (error "fail")
9

这包括fix定义中的递归调用。看看在f的定义中将最外面的(\ x -> 9)替换为fix时会发生什么:

(\ x -> 9) (fix f)

遵循与error版本完全相同的逻辑，递归调用永远不会得到评估，而您只会得到9。

关于haskell - 如何使用Y-组合器；为什么此无限递归返回9？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38902504/