haskell - 为什么这个版本的“修复”在 Haskell 中更有效？

Question

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

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

但是，这是 Haskell 实际实现它的方式（更高效）

fix f = let x = f x in x

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

Answer 1

慢的每一步都fix调用递归，而快的只调用一次。可以通过跟踪对其进行可视化：ff

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会导致为 分配惰性 thunk x，并将指向此 thunk 的指针传递给f。在第一次评估fix' f时，thunk 被评估并且所有对它的引用（这里特别是：我们传递给f的那个）都被重定向到结果值。它只是碰巧x被赋予了一个值，该值也包含对x.

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

Answer 2

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

fix (1 :)

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

Answer 3

我相信这已经被问过了，但我找不到答案。原因是第一个版本

fix f = f (fix f)

是递归函数，所以不能内联再优化。来自GHC 手册：

例如，对于自递归函数，循环断路器只能是函数本身，因此INLINE总是忽略 pragma。

但

fix f = let x = f x in x

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

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