文章/答案/技术大牛

发布

社区首页 >问答首页 >如何使用Y-组合子；为什么这个无限递归返回9？

问如何使用Y-组合子；为什么这个无限递归返回9？
EN

Stack Overflow用户

提问于 2016-08-11 17:18:41

回答 1查看 466关注 0票数 6

Y-组合器

我一直在尝试学习Y-组合器(这方面的解释也会很好)，并从这个wiki中找到了一个例子。如果能在Haskell或Python中对这一主题进行深入的解释，我们将不胜感激。求你了！

代码

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

问题

当将fix应用于(\x -> 9)时，名为fix的函数返回(\x -> 9)，我不知道为什么；当我遵循堆栈时，会可视化f(f ... (fix f) ...)。

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

haskell

functional-programming

y-combinator

fixpoint-combinators

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-08-11 17:35:01

首先，您拥有的fix函数是用直接递归实现的定点组合器。Y组合器是一种特殊的定点组合器，不需要语法递归，因此它完成了与fix相同的任务，但方式不同。

如果你好奇的话，你可以在这里看看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。

票数 11

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/38902504

复制

相似问题

问如何使用Y-组合子；为什么这个无限递归返回9？
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何使用Y-组合子；为什么这个无限递归返回9？EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何使用Y-组合子；为什么这个无限递归返回9？
EN