2

我最近参加了一场竞争性的编码比赛。

这个 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.

我也知道代码是使用 -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 )))

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

4

2 回答 2

5

是的，该n参数表现出“明显的”（对某些人而言）空间泄漏：因为不需要检查它（例如，您没有 case t 0 ... = ...），您可以在递归调用中建立添加的 thunk。

更好的是：

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

于 2018-01-14T21:43:50.180 回答
3

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

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
于 2018-01-15T07:19:17.517 回答