Haskell: Puis-je effectuer plusieurs plis sur la même liste paresseuse sans garder de liste en mémoire?

Question

Mon contexte est la bioinformatique, le séquençage de nouvelle génération en particulier, mais le problème est générique; donc je vais utiliser un fichier journal comme exemple.

Le fichier est très volumineux (Gigaoctets grand, comprimé, de sorte qu'il ne rentre pas dans la mémoire), mais est facile à analyser (chaque ligne est une entrée), donc on peut facilement écrire quelque chose comme:

parse :: Lazy.ByteString -> [LogEntry] 

Maintenant, j'ai beaucoup de statistiques que je voudrais calculer à partir du fichier journal. Il est plus facile d'écrire des fonctions distinctes, telles que:

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

Tous ces éléments sont de la forme foldl' k z . map f.

Le problème est que si comme

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 

Cette répartira toute la liste en mémoire, je tente de les utiliser de la manière la plus naturelle, ce qui est pas ce que je veux. Je veux que les plis soient faits de manière synchrone, de sorte que les cellules puissent être récupérées. Si je ne calcule qu'une seule statistique, c'est ce qui se passe.

Je peux écrire une seule grande fonction qui fait cela, mais c'est un code non-composable.

Sinon, ce que j'ai fait, je lance chaque passe séparément, mais cette recharge & décompresse le fichier à chaque fois.

Answer 1

Ce commentaire sur le commentaire de sdcvvc référence à cette 'beautiful folding' essay Il était tellement cool - beau, comme il le dit - je ne pouvais pas résister à l'ajout Functor et Applicative cas et quelques d'autres morceaux de modernisation. Pliage simultané de, disons, xy et z est un produit simple: (,,) <$> x <*> y <*> z. J'ai fait un fichier d'un demi-gigaoctet de petits nombres aléatoires et il a fallu 10 secondes pour donner le calcul - certes trivial - de la longueur, de la somme et du maximum sur mon ordinateur portable rouillé. Il ne semble pas être aidé par d'autres annotations, mais le compilateur a pu voir que Int était tout ce qui m'intéressait; le map read . lines évident comme un analyseur a conduit à une catastrophe espace et temps désespérée, donc je me suis déroulé avec une utilisation brute de ByteString.readInt; sinon, il s'agit essentiellement d'un processus 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) 

Edit: sans surprise, puisque nous avons à faire avec un type Unboxed ci-dessus, et un vecteur dérivé de unboxed par exempleun fichier 2G peut tenir dans la mémoire, tout cela est deux fois plus rapide et un peu mieux se comporter si on lui donne le reletinging évident pour Data.Vector.Uboxed http://hpaste.org/69270 Bien sûr, ce n'est pas pertinent où l'on a des types comme Notez bien que le Fold type et Fold 'multiplication' généralise sur les types séquentiels sans révision, ainsi par exemple Les plis associés aux opérations sur Char ou Word8 peuvent être simultanément pliés directement sur un ByteString. Il faut d'abord définir un foldB en relençant fold pour utiliser les foldl' dans les divers modules ByteString. Mais les Fold s et des produits de Fold s sont les mêmes que ceux que vous plier une liste ou d'un vecteur de Char s ou Word8 s

Answer 2

Pour traiter les temps de muiltiple de données paresseux, dans l'espace constant, vous pouvez faire trois choses:

• re-construire la liste paresseux à partir de zéro n fois
• fusible n passe en un seul pli séquentiel qui fait chaque étape, en étape de verrouillage.
• utilisation par faire n traversals parallèles en même temps

Ce sont vos options. Le dernier est le plus cool :)