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))

コンペティション後、テストケースが公開されました。失敗例の 1 つがこれでした: (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 )))

バンジーパターンはより多くのテストケースを通過しましたが、バングパターンも厳密な再実装もfoldl'問題を解決しませんでした。元のまだ WOMM。確かに、これは一般的に有用なスタック交換の質問の範囲から外れており、古き良き宿題のように見え始めています。これもまた、ジャッジ システムの知識がなければ、かなりデバッグ不可能です。

4

2 に答える 2