Haskell程序的奇怪空间行为

Question

我认为Contmonad只相当于CPS Transformation,所以如果我有一个monadic总和,如果我在Identitymonad中运行,它将因堆栈溢出而失败,如果我在ContMonad中运行它,它将没关系,因为尾递归.

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

所有程序都是使用编译的 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需要这里,因为它的延续直到n0 才会应用.

• 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是Contmonad).为什么？

• main = print (sum3 3000000 (const 0))
  使用大量内存.我认为sum3相当于sum1(Contmonad).为什么？

• 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))：成功，分配量大约为 70%sum1
• main = print (sum3 3000000 (const 0))：成功，分配量大约为 50%sum1
• main = print (runIdentity (sum1 3000000))：堆栈溢出，分配很少
• main = print (sum3 3000000 id)：成功，分配量大约为 50%sum1
• main = print (sum4 3000000 id)：成功，分配量大约为 50%sum1
• main = print (sum [1 .. 3000000])：堆栈溢出，分配量约为 80%sum1
• main = print (foldl' (+) 0 [1 .. 3000000])：成功，几乎没有分配

所以这基本上就是你所期望的，除了为什么与 .seq之间有如此大的差异。sum1sum5