在做GHC解释器的某些情况下只有空间泄漏:concat <some list> !! ñ

Question

我定义我自己的版本concat,myConcat:

module Eh where

myConcat []          = []
myConcat ([]:os)     = myConcat os
myConcat ((x:xs):os) = x : myConcat (xs:os)

(!!!)  :: [a] -> Int -> a
xs     !!! n | n < 0 = error "negative index"
[]     !!! _         = error "index too large"
(x:_)  !!! 0         = x
(_:xs) !!! n         = xs !!! (n-1)

如果我myConcat <some huge list> !! n使用GHC解释器,它会以300MB/s的速度窃取我的内存,而且我必须在它召唤OOM杀手之前杀死它.请注意,我加载Eh为"解释",我在加载之前不编译它.

code run in the GHC interpreter        space leak?
myConcat (repeat [1,2,3,4]) !! (10^8)  Yes
concat (repeat [1,2,3,4]) !! (10^8)    No
myConcat (repeat [1,2,3,4]) !!! (10^8) No
concat (repeat [1,2,3,4]) !!! (10^8)   No

现在,如果我编译Eh(ghc --make -O2 Eh.hs),然后在解释器中加载它并重新运行这些测试,它们都没有空间泄漏.如果我编译每个测试用例而不是在解释器中运行它们,则相同.

这是怎么回事？

---

我正在运行GHC 6.12.3.

Answer 1

这里的问题是严格性。Haskell 中的计算是不严格的，因此通常仅在确实需要结果时才执行计算。相反，会创建一个所谓的 thunk 来表示尚未执行的计算。

然而，在某些情况下，编译器可以检测到无论如何都需要计算结果，因此用实际计算替换 thunk 的创建。

Haskell Wiki可能对此有更好的解释。

要修复您的myConcat函数，您必须确保它不会通过手动强制严格评估来创建数百万个重击。一种（看起来不太漂亮）的方法可能是：

myConcat []          = []
myConcat ([]:os)     = myConcat os
myConcat ((x:xs):os) = ((:) $! x) myConcat (xs:os)