为什么这个版本的'fix'在哈斯克尔更有效率？

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 会导致一个懒惰的 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杂注。

但

fix f = let x = f x in x

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

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