Faule Dekodierung einer Liste mit Data.Binary

Question

ich faul bin codiert, Listen mit diesem Code (aus diesem SO question genommen):

import Data.Binary 

newtype Stream a = Stream { unstream :: [a] } 

instance Binary a => Binary (Stream a) where 

    put (Stream [])  = putWord8 0 
    put (Stream (x:xs)) = putWord8 1 >> put x >> put (Stream xs) 

Das Problem ist, dass die Decodierung Implementierung ist nicht faul:

get = do 
     t <- getWord8 
     case t of 
      0 -> return (Stream []) 
      1 -> do x   <- get 
        Stream xs <- get 
        return (Stream (x:xs)) 

mir Das sieht aus wie es faul sein sollte, aber wenn wir diesen Test-Code ausführen:

head $ unstream (decode $ encode $ Stream [1..10000000::Integer] :: Stream Integer) 

Speicher Nutzung explodiert. Aus irgendeinem Grund will es die ganze Liste entschlüsseln, bevor ich das erste Element betrachten kann.

Warum ist das nicht faul, und wie kann ich es faul machen?

Answer 1

Es ist nicht faul, weil die Get Monade ein strenger Zustand Monade (in binary-0.5.0.2 to 0.5.1.1 ist, es ist ein fauler Zustand Monade vorher war, und in binary-0.6.* hat es eine Fortsetzung Monade geworden, ich habe nicht die Strenge Auswirkungen dieser Änderung analysiert):

-- | The parse state 
data S = S {-# UNPACK #-} !B.ByteString -- current chunk 
      L.ByteString     -- the rest of the input 
      {-# UNPACK #-} !Int64   -- bytes read 

-- | The Get monad is just a State monad carrying around the input ByteString 
-- We treat it as a strict state monad. 
newtype Get a = Get { unGet :: S -> (# a, S #) } 

-- Definition directly from Control.Monad.State.Strict 
instance Monad Get where 
    return a = Get $ \s -> (# a, s #) 
    {-# INLINE return #-} 

    m >>= k = Get $ \s -> case unGet m s of 
          (# a, s' #) -> unGet (k a) s' 
    {-# INLINE (>>=) #-} 

somit die letzte rekursive

get >>= \x -> 
get >>= \(Stream xs) -> 
return (Stream (x:xs)) 

zwingt die gesamte Stream gelesen werden, bevor sie zurückgegeben werden können.

Ich glaube nicht, dass es möglich ist, Stream in der Get Monade träge zu decodieren (also erst recht nicht mit der Binary Instanz). Aber Sie können eine faule Dekodierungsfunktion mit runGetState schreiben:

-- | Run the Get monad applies a 'get'-based parser on the input 
-- ByteString. Additional to the result of get it returns the number of 
-- consumed bytes and the rest of the input. 
runGetState :: Get a -> L.ByteString -> Int64 -> (a, L.ByteString, Int64) 
runGetState m str off = 
    case unGet m (mkState str off) of 
     (# a, ~(S s ss newOff) #) -> (a, s `join` ss, newOff) 

zuerst einen Get Parser schreiben, die ein Maybe a zurückzugibt,

getMaybe :: Binary a => Get (Maybe a) 
getMaybe = do 
    t <- getWord8 
    case t of 
     0 -> return Nothing 
     _ -> fmap Just get 

dann verwenden, eine Funktion vom Typ zu machen (ByteString,Int64) -> Maybe (a,(ByteString,Int64)):

step :: Binary a => (ByteString,Int64) -> Maybe (a,(ByteString,Int64)) 
step (xs,offset) = case runGetState getMaybe xs offset of 
        (Just v, ys, newOffset) -> Just (v,(ys,newOffset)) 
        _      -> Nothing 

und dann können Sie Data.List.unfoldr verwenden, um eine Liste langsam zu decodieren,

lazyDecodeList :: Binary a => ByteString -> [a] 
lazyDecodeList xs = unfoldr step (xs,0) 

und wickeln, dass in einem Stream

lazyDecodeStream :: Binary a => ByteString -> Stream a 
lazyDecodeStream = Stream . lazyDecodeList