Haskell: Kann ich mehrere Faltungen über dieselbe faule Liste durchführen, ohne die Liste im Speicher zu behalten?

Question

Mein Kontext ist Bioinformatik, insbesondere Sequenzierung der nächsten Generation, aber das Problem ist generisch; Daher werde ich eine Protokolldatei als Beispiel verwenden.

Die Datei ist sehr groß (Gigabytes groß, komprimiert, so dass es nicht in den Speicher passen wird), ist aber leicht zu analysieren (jede Zeile ein Eintrag), so können wir leicht so etwas wie schreiben:

parse :: Lazy.ByteString -> [LogEntry] 

Jetzt habe ich viele Statistiken, die ich aus der Protokolldatei berechnen möchte. Am einfachsten ist es separate Funktionen schreiben wie:

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

All diese sind von der Form foldl' k z . map f.

Das Problem ist, dass, wenn ich versuche, sie auf der natürlichste Art und Weise zu verwenden, wie

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 

Dies wird die gesamte Liste im Speicher zuweisen, das nicht das, was ich will. Ich möchte, dass die Falten synchron gemacht werden, damit die Cons-Zellen Müll gesammelt werden können. Wenn ich nur eine einzige Statistik berechne, passiert das.

Ich kann eine einzelne große Funktion schreiben, die dies tut, aber es ist nicht zusammensetzbaren Code.

Alternativ, was ist, was ich getan habe, ich jeden Durchlauf separat ausführen, aber das & lädt die Datei jedes Mal dekomprimiert.

Answer 1

Dies ist ein Kommentar auf den Kommentar von sdcvvc diese 'beautiful folding' essay bezieht Es war so cool - schön, wie er sagt - ich konnte nicht widerstehen Zugabe Functor und Applicative Instanzen und ein paar andere Teile der Modernisierung. Das gleichzeitige Falten von beispielsweise xy und z ist ein einfaches Produkt: (,,) <$> x <*> y <*> z. Ich machte eine halbe Gigabyte Datei mit kleinen zufälligen Ints und es dauerte 10 Sekunden, um die - zugegebenermaßen triviale - Berechnung von Länge, Summe und Maximum auf meinem rostigen Laptop zu machen. Es scheint nicht durch weitere Anmerkungen geholfen zu werden, aber der Compiler konnte sehen, Int war alles, was ich interessiert war; die offensichtliche map read . lines als Parser führte zu einer hoffnungslosen Raum und Zeit Katastrophe, so entfaltete ich mit einem groben Gebrauch von ByteString.readInt; ansonsten ist es im Grunde ein Data.List Prozess.

{-# 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: wenig überraschend, da wir oben mit einer unboxed Art zu tun, und einem unboxed Vektor von zum Beispiel abgeleiteteine 2G-Datei kann in den Speicher passen, das ist alles doppelt so schnell und etwas besser verhielt, wenn es das offensichtliche Nachladen für Data.Vector.Uboxed http://hpaste.org/69270 Natürlich ist dies nicht relevant, wenn man Typen wie LogEntry hat Beachten Sie, dass die Fold type und Fold "multiplication" verallgemeinert sequentielle Typen ohne Revision, also z Die mit Operationen an Char s oder Word8 verbundenen Faltungen können gleichzeitig direkt über einen ByteString gefaltet werden. Man muss zuerst einen foldB definieren, indem man fold neu lädt, um die foldl' s in den verschiedenen ByteString Modulen zu verwenden. Aber die Fold s und Produkte von Fold s sind die gleichen, die Sie eine Liste oder Vektor Char s falten würde oder Word8 s

Answer 2

Zu faul Daten muiltiple Zeiten, in konstanten Raum zu bearbeiten, können Sie drei Dinge tun:

• die faule Liste von Grund auf re-build n mal
• Sicherung n einem einzigen geht in sequentielle Faltung, die jeden Schritt ausführt, im Sperrschritt.
• Verwendung parn parallel Traversierungen zugleich

Das sind Ihre Möglichkeiten zu tun. Die letzte ist die coolste :)