performance - Haskell 程序的奇怪空间行为

Question

我以为 Cont monad 就相当于 CPS 转换，所以如果我有
一个单子(monad)总和，如果我在 Identity 中运行monad，它将由于堆栈溢出而失败，如果
我在 Cont 中运行它Monad，由于尾递归，它会没事的。

所以我写了一个简单的程序来验证我的想法。但令我惊讶的是，由于我的知识有限，结果是不合理的。

所有程序均使用 ghc --make Test.hs -o test && ./test 编译

sum0 n = if n==0  then  0  else n + sum0 (n-1)
sum1 n = if  n==0  then return 0 else sum1 (n-1) >>= \ v ->  seq v (return (n+v))
sum2 n k = if n == 0 then k 0 else sum2 n (\v -> k (n + v))
sum3 n k = if n == 0 then k 0 else sum3 n (\ !v -> k (n + v))
sum4 n k = if n == 0 then k 0 else sum4 n (\ v -> seq v ( k (n + v)))
sum5 n = if  n==0  then return 0 else sum5 (n-1) >>= \ v ->   (return (n+v)) 

main = print (sum0 3000000)堆栈溢出。这是合理的。

main = print (flip runCont id (sum1 3000000))使用180M内存，这是合理的，但我不清楚为什么seq这里需要，因为它的延续直到 n 才应用。转到 0。

main = print (flip runCont id (sum5 3000000))堆栈溢出。为什么？

main = print (flip runCont (const 0) (sum1 3000000))使用 130M 内存。这是合理的。

main = print (flip runCont (const 0) (sum5 3000000))使用 118M 内存。这是合理的。

main = print (sum2 3000000 (const 0))使用大量内存(超过 1G)。我以为 sum2相当于sum5 (当 sum5 在 Cont 单子(monad)中时)。为什么？

main = print (sum3 3000000 (const 0))使用大量内存。我以为 sum3相当于sum1 (Cont 单子(monad))。为什么？

main = print (runIdentity (sum1 3000000))堆栈溢出，正是我想要的。

main = print (sum3 3000000 id)使用大量内存。相当于 sum1 ， 为什么？

main = print (sum4 3000000 id)使用大量内存。相当于sum1，为什么？

main = print (sum [1 .. 3000000])堆栈溢出。 sum = foldl (+) 0的来源| ，所以这是合理的。

main = print (foldl' (+) 0 [1 .. 3000000])使用 1.5M。

Answer 1

首先，在我看来它像 sum2 , sum3 , 和 sum4从未真正减少 n .所以他们使用了大量内存，因为他们进入了一个执行分配的无限循环。

更正后，我再次运行您的每个测试，结果如下，其中“分配”指的是近似的峰值内存使用:

main = print (sum0 3000000) : 堆栈溢出，分配很少的内存后

main = print (flip runCont id (sum1 3000000)) : 成功，分配与你看到的相似的数量

main = print (flip runCont id (sum5 3000000)) : 堆栈溢出，在分配与 sum1 相似的内存量之后.

main = print (flip runCont (const 0) (sum1 3000000)) : 成功，类似上面的分配

main = print (flip runCont (const 0) (sum5 3000000)) : 相同

main = print (sum2 3000000 (const 0)) : 成功，大约是 sum1 的 70%

main = print (sum3 3000000 (const 0)) : 成功，分配量大约为 sum1 的 50%

main = print (runIdentity (sum1 3000000)) : 堆栈溢出，分配很少

main = print (sum3 3000000 id) : 成功，分配量大约为 sum1 的 50%

main = print (sum4 3000000 id) : 成功，分配量大约为 sum1 的 50%

main = print (sum [1 .. 3000000]) : 堆栈溢出，分配量约为 sum1 的 80%

main = print (foldl' (+) 0 [1 .. 3000000]) : 成功，几乎没有分配

所以这主要是你所期望的，除了为什么 seq sum1 之间的差异如此之大与 sum5 .