GHC何时使用共享？

Question

一个初学者的问题.我对以下内容感到有点困惑:我读过GHC(Haskell的？)懒惰评估方法包括使用共享,所以例如评估表达式

(1+1)*(1+1)

只计算1+1一次.在格雷厄姆·赫顿(Graham Hutton)的"在哈斯克尔编程"(Programming in Haskell)一书中解释说,这是通过用1+1指针的一个副本替换它的两个出现并仅评估那个副本来实现的.

但是计算第n个斐波纳契数是指n中的fib n = if (n<2) then n else fib (n-1) + fib(n-2)指数时间.我的上述不足之处告诉我,例如fib 5将按如下方式进行评估:

fib 5 => fib 4 + fib 3 => fib 3 + fib 2 + fib 3 => x + fib 2 + x

同 x = fib 3 = fib 2 + fib 1 = y + fib 1

所以 fib 5 = y + fib 1 + y + y + fib 1

同 y = fib 2 = fib 1 + fib 0 = 1

所以 fib 5 = 1 + 1 + 1 + 1 + 1

在哪里x和y作为共享值引入.

但是这种方式进行的,而不是迭代产生的标准方式有点低效率fib k的2<=k<=n,显然也不会在这么长的运行时间为导致评估实际上做的功能.那么我的理解有什么不对？

Answer 1

您不能依赖于GHC中的公共子表达式消除(由于技术原因,共享惰性值可能会引入空间泄漏).

一个好的经验法则是值由名称共享.因此,请为您的子表达式命名,如下所示:

 n * n
    where n = 1 + 1

你保证分享.

请注意,在您的简单示例中,GHC将在编译时计算整个事物.以上讨论实际上仅适用于"大"数据.

您可以使用vacuum等调试工具观察共享.此类共享值表示为具有多个引用的堆分配对象: