Haskell: Могу ли я выполнить несколько сгибов в том же ленивом списке, не сохраняя список в памяти?

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

Файл очень большой (Gigabytes большой, сжатый, поэтому он не поместится в памяти), но легко разобрать (каждая строка является записью), поэтому мы можем легко написать что-то вроде:

parse :: Lazy.ByteString -> [LogEntry]

Теперь у меня есть много статистики, которые я хотел бы вычислить из файла журнала. Легче всего написать отдельные функции, такие как:

totalEntries = length
nrBots = sum . map fromEnum . map isBotEntry
averageTimeOfDay = histogram . map extractHour

Все они имеют вид foldl' k z . map f.

Проблема в том, что если я попытаюсь использовать их наиболее естественным образом, например

main = do
    input <- Lazy.readFile "input.txt"
    let logEntries = parse input
        totalEntries' = totalEntries logEntries
        nrBots' = nrBots logEntries
        avgTOD = averageTimeOfDay logEntries
    print totalEntries'
    print nrBots'
    print avgTOD

Это выделит весь список в памяти, который я не хочу. Я хочу, чтобы складки делались синхронно, так что ячейки cons могут быть собраны в мусор. Если я вычисляю только одну статистику, это то, что происходит.

Я могу написать одну большую функцию, которая делает это, но это неконсолидируемый код.

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

Ответы

Ответ 1

Это комментарий к комментарию sdcvvc, относящийся к этому "красивому складному" эссе. Это было так здорово - красиво, как он говорит - я не мог сопротивляться добавлению экземпляров Functor и Applicative и нескольких других модификаций. Одновременное складывание, скажем, x y и z является простым произведением: (,,) <$> x <*> y <*> z. Я сделал полугигабайтный файл с небольшими случайными ints, и потребовалось 10 секунд, чтобы дать - по общему признанию тривиальный - вычисление длины, суммы и максимума на моем ржавом ноутбуке. По-видимому, этому не помогают дальнейшие аннотации, но компилятор мог видеть, что Int было всем, что меня интересовало; очевидный map read . lines как синтаксический анализатор привел к безнадежной космической и временной катастрофе, поэтому я развернулся с грубым использованием ByteString.readInt; в противном случае это в основном процесс Data.List.

{-# LANGUAGE GADTs, BangPatterns #-}

import Data.List (foldl', unfoldr)
import Control.Applicative 
import qualified Data.ByteString.Lazy.Char8 as B

main = fmap readInts (B.readFile "int.txt") >>= print . fold allThree
  where allThree = (,,) <$> length_ <*> sum_ <*> maximum_

data Fold b c where  F ::  (a -> b -> a) -> a -> (a -> c) -> Fold b c
data Pair a b = P !a !b

instance Functor (Fold b) where  fmap f (F op x g) = F op x (f . g)

instance Applicative (Fold b) where
  pure c = F const () (const c)
  (F f x c) <*> (F g y c') = F (comb f g) (P x y) (c *** c')
    where comb f g (P a a') b = P (f a b) (g a' b)
          (***) f g (P x y) = f x ( g y)

fold :: Fold b c -> [b] -> c
fold (F f x c) bs = c $ (foldl' f x bs)

sum_, product_ :: Num a => Fold a a
length_ :: Fold a Int
sum_     = F (+) 0 id
product_ = F (*) 1 id
length_  = F (const . (+1)) 0 id
maximum_ = F max 0 id
readInts  = unfoldr $ \bs -> case B.readInt bs of
  Nothing      -> Nothing
  Just (n,bs2) -> if not (B.null bs2) then Just (n,B.tail bs2) 
                                      else Just (n,B.empty)

Изменить: неудивительно, так как мы имеем дело с вышеперечисленным типом выше, и unboxed вектор, полученный из, например, файл 2G может поместиться в память, это все в два раза быстрее и несколько лучше, если ему дается очевидное перераспределение для Data.Vector.Uboxed http://hpaste.org/69270 Конечно это не имеет значения, если у вас есть такие типы, как LogEntry Обратите внимание, что тип Fold и Fold "умножение" обобщают на последовательные типы без пересмотра, таким образом, например Folds, связанные с операциями на Char или Word8, могут быть одновременно сведены непосредственно над ByteString. Сначала нужно определить a foldB путем перераспределения Fold, чтобы использовать foldl' в различных модулях ByteString. Но Fold и продукты Fold - это те же самые, что вы бы сбросили список или вектор Char или Word8 s

Ответ 2

Чтобы обрабатывать ленивые данные muiltiple раз, в постоянном пространстве, вы можете сделать три вещи:

  • повторно создайте ленивый список с нуля n раз
  • плавкий предохранитель n переходит в единую последовательную складку, которая выполняет каждый шаг, на этапе блокировки.
  • использовать par для одновременного выполнения параллельных обходов

Это ваши варианты. Последний самый крутой:)