haskell - 如何使用 Y-Combinator；为什么这个无限递归返回 9？

Question

Y - 组合器

我一直在尝试了解 Y-Combinators （对此的解释也很可爱），并从这个wiki遇到了一个例子。在 Haskell 或 Python 中对该主题进行深入的解释将不胜感激。请！

代码

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

问题

调用的函数在应用于时fix返回，我不知道为什么；当我跟随我想象的堆栈时。9fix(\x -> 9)f(f ... (fix f) ...)

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

Answer 1

首先：您拥有的功能是一个用直接递归实现fix的定点组合器。Y 组合器是一个特定的定点组合器，它不需要语法递归，因此它完成了相同的事情，但方式不同。fix

如果你很好奇，你可以在 SO 上查看如何在 Haskell 中实现 Y 组合器。静态类型有点棘手——它需要递归类型才能工作。

至于你的第二个问题，由于懒惰，代码可以工作。如果你申请(\ x -> 9)任何东西，那东西永远不会被评估。尝试这个：

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

这包括定义中的递归调用fix。看看当你用 的定义替换最外层时会f发生(\ x -> 9)什么fix：

(\ x -> 9) (fix f)

遵循与带有 的版本完全相同的逻辑error，递归调用永远不会被评估，你只会得到一个9输出。