为什么这个版本的 '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 (fix f)

是递归函数，所以不能内联再优化。来自 GHC manual:

For example, for a self-recursive function, the loop breaker can only be the function itself, so an INLINE pragma is always ignored.

但是

fix f = let x = f x in x

不是递归的，递归被移动到 let 绑定中，因此可以内联它。

更新： 我做了一些测试，虽然前一个版本没有内联而后者有，但它似乎对性能并不重要。所以其他解释（堆上的单个对象与每次迭代创建一个对象）似乎更准确。

Answer 2

慢的 fix 在递归的每一步调用 f，而快的 f 只调用一次。可以用tracing可视化：

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 的引用。

我承认这可能相当令人费解。懒惰是一个人应该习惯的事情。

Answer 3

我认为当您调用 fix 时使用一个带有两个参数的函数来生成一个带有一个参数的函数时，这并不总是（或不一定）有帮助。您必须 运行 一些基准才能看到。但是你也可以用一个带一个参数的函数来调用它！

fix (1 :)

是一个循环链表。使用 fix 的天真定义，它将是一个无限列表，随着结构的强制，新的片段被懒惰地构建。