haskell - 为什么这个版本的 'fix' 在 Haskell 中效率更高？

Question

在 Haskell 中，这是一个固定点的简单(朴素)定义

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

但是，这是 Haskell 实际实现它的方式(更高效)

fix f = let x = f x in x

我的问题是为什么第二个比第一个更有效？

Answer 1

慢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 的引用.

我承认这可能相当令人费解。与懒惰一起工作时应该习惯这一点。