Space Haskell 中的泄漏 - 旧编译器的错误还是我的？显然是后者

Question

我最近参加了一个编码竞赛。

这 Haskell 在判断系统运行 ghc 7.6.3:

上造成了 space 泄漏

t n [] = 0
t n ('8':rest) = t (n+1) rest
t n (')':rest) = n + (t n rest)

main = getLine >>= (\l -> print (t 0 l))

比赛结束后公布了测试用例。失败案例之一是：（一个包含 10^5 个右括号的文件）：https://cses.fi/download/1/b575d19a75bf724b50fa4a399f8187b6d6edb4ccb62bd1a774f9294969152e46

错误是

Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it.

我也知道代码是在我认为是 GHC 7.6.3 上用 -O2 和 -Wall 编译的。

我这辈子都无法在我的机器上使用 GHC 8.0.2 或 7.10.3 重现错误。

代码中是否存在明显的space漏洞？

编辑：

我按照下面的建议测试了代码，并因此实现了折叠：

import Data.Foldable

t (kasit, score) '8' = (kasit+1, score)
t (kasit, score) _ = (kasit, score+kasit)

main = getLine >>= (\l -> print (snd (foldl' (t) (0, 0) l )))

bang 模式和严格 foldl' 的重新实现都没有解决问题，尽管 bangy 模式通过了更多测试用例。原来还是WOMM。诚然，这超出了通常有用的堆栈交换问题的范围，开始看起来像是很好的旧作业。如果不了解判断系统，这也是非常不可调试的。

Answer 1

是的，n 参数表现出 "obvious"（对某些人而言）space 泄漏：因为它不需要检查（例如，您没有案例t 0 ... = ...) 你可以在你的递归调用中增加thunks。

更好的是：

t _ [] = 0
t !n ('8':rest) = t (n+1) rest
t !n (')':rest) = n + (t n rest)

最好用 foldl'.

来定义它

完全有可能比 7.6 更新的 GHC 版本可以更好地分析严格性和优化此代码。

有用的事实，强制堆栈溢出是查找 space 泄漏（通常表现为堆使用）的有效方法：http://neilmitchell.blogspot.com/2015/09/detecting-space-leaks.html

Answer 2

我认为你的最后一个案例给你带来了麻烦。你写了

t n [] = 0
t n ('8':rest) = t (n+1) rest
t n (')':rest) = n + (t n rest)

即使我们按照 jberryman 的建议对其进行严格限制，

t !n [] = 0
t !n ('8':rest) = t (n+1) rest
t !n (')':rest) = n + (t n rest)

第三种情况不是尾递归。我们如何解决这个问题？只需在末尾添加另一个代表要添加的金额的累加器。

t n0 xs = t' 0 n0 xs
  where
    t' !acc !_n [] = acc
    t' acc n ('8':rest) = t' acc (n + 1) rest
    t' acc n (')':rest) = t' (acc + n) n rest

Space Haskell 中的泄漏 - 旧编译器的错误还是我的？显然是后者

Space leak in Haskell - old compiler's fault or mine? Apparently the latter

haskell

ghc

space-leak