Haskell: ¿Puedo realizar varios pliegues sobre la misma lista perezosa sin mantener la lista en la memoria?

Question

Mi contexto es la bioinformática, la secuenciación de próxima generación en particular, pero el problema es genérico; entonces usaré un archivo de registro como ejemplo.

El archivo es muy grande (Gigabytes grande, comprimido, por lo que no cabe en la memoria), pero es fácil de analizar (cada línea es una entrada), por lo que fácilmente puede escribir algo como:

parse :: Lazy.ByteString -> [LogEntry] 

Ahora, tengo muchas estadísticas que me gustaría calcular a partir del archivo de registro. Es más fácil de escribir funciones separadas, tales como:

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

Todos estos son de la forma foldl' k z . map f.

El problema es que si trato de usarlos de la manera más natural, como

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 

Esto le asigne toda la lista en la memoria, lo cual no es lo que quiero. Quiero que los pliegues se hagan de forma sincrónica, para que las celdas de cons puedan ser recogidas. Si calculo solo una estadística, esto es lo que sucede.

Puedo escribir una sola función grande que hace esto, pero es un código que no se puede componer.

Alternativamente, que es lo que he estado haciendo, ejecuto cada pase por separado, pero esto vuelve a cargar & descomprime el archivo cada vez.

Answer 1

Este comentario sobre el comentario de sdcvvc refería a esta 'beautiful folding' essay Es muy interesante - hermoso, como él dice - no podía resistirse a añadir Functor y Applicative casos y unos pocos otros bits de modernización. Plegado simultáneo de, por ejemplo, xy y z es un producto sencillo: (,,) <$> x <*> y <*> z. Hice un archivo de medio gigabyte de pequeñas entradas aleatorias y me tomó 10 segundos dar el cálculo, ciertamente cierto, de longitud, suma y máximo en mi laptop oxidada. No parece ser ayudado por anotaciones adicionales, pero el compilador podía ver Int era todo lo que me interesaba; el obvio map read . lines como analizador condujo a una catástrofe espacial y temporal sin esperanza, así que desarrollé con un uso crudo de ByteString.readInt; de lo contrario, es básicamente un proceso 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) 

Editar: como era de esperar, ya que tenemos que hacer con un tipo de unboxed anteriormente, y un vector de unboxed derivado de, por ejemplo,un archivo 2G puede caber en la memoria, esto es todo el doble de rápido y se comportó mejor si se le da el relettering obvio para Data.Vector.Uboxed http://hpaste.org/69270 Por supuesto, esto no es relevante donde uno tiene tipos como LogEntry Tenga en cuenta que el Fold type y Fold 'multiplication' generaliza sobre tipos secuenciales sin revisión, por lo tanto, por ejemplo los pliegues asociados con las operaciones en Char so Word8 s se pueden plegar simultáneamente sobre ByteString. Primero debe definir un foldB, al releer fold para usar el foldl' s en los diversos módulos ByteString. Pero los Fold s y productos de Fold s son los mismos que se doblarían una lista o vector de Char s o s Word8

Answer 2

Para procesar veces muiltiple datos perezosos, en el espacio constante, puede hacer tres cosas:

• reconstruir la lista perezosa de cero n veces
• fusibles n pasa en una sola pliegue secuencial que hace cada paso, en el paso de bloqueo.
• par hacer uso n recorridos paralelos al mismo tiempo

Esos son sus opciones. El último es el más fresco :)