haskell - Haskell 中的空间泄漏——旧编译器的错还是我的错？显然是后者

Question

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

这个 Haskell 在运行 ghc 7.6.3 的判断系统上造成了空间泄漏:

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 重现错误。

代码中是否存在明显的空间泄漏？

编辑:

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

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 参数表现出“明显的”(对某些人而言)空间泄漏:因为它不需要检查(例如，您没有 case t 0 ... = ...) 你可以在你的递归调用中增加thunks。

更好的做法是:

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

最好用 foldl' 来定义它。

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

有用的事实，强制堆栈溢出是发现空间泄漏(通常表现为堆使用)的有效方法:http://neilmitchell.blogspot.com/2015/09/detecting-space-leaks.html