Утечка пространства в 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.

Я также знаю, что код был скомпилирован с -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 ... = ...) вы можете создавать множество дополнений в ваших рекурсивных вызовах.

Лучше было бы что-то вроде:

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

лучше всего было бы, вероятно, определить это с точки зрения foldl',

Вполне возможно, что более новая версия GHC, чем 7.6, будет лучше анализировать строгость и оптимизировать этот код.

Полезный фактоид, принудительное переполнение стека может быть эффективным способом обнаружения утечек пространства (что обычно проявляется в использовании кучи): 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