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个关闭的parens的文件)​​:https://cses.fi/download/1/b575d19a75bf724b50fa4a399f8187b6d6edb4ccb62bd1a774f9294969152e46

错误是

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

我也知道代码是用-O2和-Wall编译的,我认为是GHC 7.6.3.

对于我的生活,我无法在我的机器上使用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 )))

无论是爆炸模式还是严格的重新实现都没有foldl'解决问题,尽管这个模型通过了更多的测试用例.原来仍然是WOMM.不可否认,这超出了通常有用的堆栈交换问题的范围,并开始看起来像旧的功课.如果不了解法官制度,这也是不可判断的.

Answer 1

是的,该n参数表现出"明显的"(某些)空间泄漏:因为它不需要检查(例如,您没有案例t 0 ... = ...),您可以在递归调用中构建添加的thunk.

更好的是:

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

最好的可能就是用这个来定义foldl'.

更新版本的GHC比7.6更有可能在分析严格性和优化此代码方面做得更好.

有用的factoid,强制堆栈溢出可以是查找空间泄漏的有效方法(通常表现为堆使用):http://neilmitchell.blogspot.com/2015/09/detecting-space-leaks.html