Чтение большого файла в haskell? - программирование

Я пытался прочитать большой файл в haskell.

Мне нужно сжать его с помощью пользовательского алгоритма для университетского проекта. Все работает отлично до тех пор, пока я не начну сжимать большие файлы.

Я извлек из неё что-то не так, и я разоблачил его здесь в форме "Hello big file":

import System
import qualified Data.ByteString.Lazy as BL
import Data.Word

fold_tailrec :: (a -> b -> a) -> a -> [b] -> a
fold_tailrec _ acc [] =
    acc
fold_tailrec foldFun acc (x : xs) =
    fold_tailrec foldFun (foldFun acc x) xs

fold_tailrec' :: (a -> b -> a) -> a -> [b] -> a
fold_tailrec' _ acc [] =
    acc
fold_tailrec' foldFun acc (x : xs) =
    let forceEval = fold_tailrec' foldFun (foldFun acc x) xs in
    seq forceEval forceEval

main :: IO ()
main =
    do
        args <- System.getArgs
        let filename = head args
        byteString <- BL.readFile filename
        let wordsList = BL.unpack byteString
        -- wordsList is supposed to be lazy (bufferized)
        let bytesCount = fold_tailrec (\acc word -> acc + 1) 0 wordsList
        print ("Total bytes in " ++ filename ++ ": " 
               ++ (show bytesCount))

Я называю этот файл Test.hs, а затем делаю следующее:

$ ls -l toto
-rwxrwxrwx 1 root root 5455108 2011-03-23 19:08 toto
$ ghc --make -O Test.hs
[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking Test ...
$ ./Test toto
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
$ ./Test toto +RTS -K50M -RTS
Stack space overflow: current size 50000000 bytes.
Use `+RTS -Ksize -RTS' to increase it.
$ ./Test toto +RTS -K500M -RTS
"Total bytes in toto: 5455108"
$ time ./Test toto +RTS -K500M -RTS
"Total bytes in toto: 5455108"

real    0m33.453s
user    0m8.917s
sys 0m10.433s

Может кто-нибудь объяснить, почему мне нужно 500 мегабайт оперативной памяти и 30 секунд процессора, чтобы просмотреть жалкий 5 мегабайт файл? Пожалуйста, что я делаю неправильно? Почему буфер [word8] не буферизуется, поскольку документация ByteString указывается. И как это исправить?

Я попытался определить собственную хвостовую рекурсивную складку вместо foldl, foldr или foldl '. Я также попытался разморозить трюки с помощью seq. Пока я не получил результата.

Спасибо за любую помощь, потому что я застрял.

Ответ 1

Конструкция "seq x x" всегда бесполезна. Если y = seq x x и я принудительно y, то это заставляет x затем возвращает x. Это эквивалентно y = x и принуждению y. Таким образом, "seq forceEval forceEval" делает не что иное, как "forceEval".

Ошибка при использовании складки является общей.

Вы используете сгиб, чтобы выполнить подсчет байтов на входе. Вы должны использовать строчную левую складку для такой суммы, но ваша рукописная складка - это ленивая левая складка. (Acc + 1) не получает оценку, поэтому он строит 5 миллионов вложенных приложений: (((... (0 + 1) +1) +1) +1) +1) +1)... + 1). Затем он вынужден при печати, и оценка пытается спуститься в 5 миллионов круглых скобок.

Таким образом, ожидающий стек имеет одну запись для каждого Word8. Для коротких входов он достигает конца и видит 0. Для длинных входов он заканчивается из пространства стека с GHC, потому что создатели и большинство пользователей GHC считают, что попытка выделить 5 миллионов кадров стека обычно является ошибкой дизайна программистом.

Я предсказываю, что вы можете использовать "seq", чтобы исправить это:

fold_tailrec' foldFun acc (x : xs) =
    let acc' = foldFun acc x
    in seq acc' (fold_tailrec' foldFun acc' xs)