为什么这个版本的“修复”在Haskell中更有效？
为什么这个版本的“修复”在Haskell中更有效？
提问于 2016-05-22 01:45:23
在Haskell中，这是固定点的简单(幼稚)定义
fix :: (a -> a) -> a
fix f = f (fix f)但是，以下是Haskell实际实现它的方式(更有效)
fix f = let x = f x in x我的问题是，为什么第二个比第一个更有效？
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-05-22 02:01:47
慢的fix在递归的每一步都调用f，而快的只调用f一次。它可以通过跟踪来可视化：
import Debug.Trace
fix f = f (fix f)
fix' f = let x = f x in x
facf :: (Int -> Int) -> Int -> Int
facf f 0 = 1
facf f n = n * f (n - 1)
tracedFacf x = trace "called" facf x
fac = fix tracedFacf
fac' = fix' tracedFacf现在试着跑一跑：
> fac 3
called
called
called
called
6
> fac' 3
called
6更详细地说，let x = f x in x会导致为x分配一个懒惰的thunk，并将指向此thunk的指针传递给f。在第一次计算fix' f时，thunk会被计算，所有对它的引用(这里特别是:我们传递给f的引用)都会被重定向到结果值。恰好x被赋予了一个也包含对x的引用的值。
我承认这可能是相当令人费解的。这是一个人在与懒惰一起工作时应该习惯的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/37366222
复制相关文章
相似问题