Serialización binaria para listas de longitud indefinida en Haskell

Question

He estado utilizando Data.Binary para serializar datos en archivos. En mi aplicación, agrego elementos a estos archivos de forma incremental. Los dos paquetes de serialización más populares, binarios y de cereal, ambos serializan las listas como un recuento seguido de los elementos de la lista. Debido a esto, no puedo agregar a mis archivos serializados. Actualmente leo en el archivo completo, deserializo la lista, anexo a la lista, serializo nuevamente la lista y la vuelvo a escribir en el archivo. Sin embargo, mi conjunto de datos es cada vez más grande y me estoy quedando sin memoria. Probablemente podría ir unboxing mis estructuras de datos para ganar algo de espacio, pero ese enfoque no escala.

Una solución sería ensuciarse con el formato de archivo para cambiar el recuento inicial, luego solo anexar mis elementos. Pero eso no es muy satisfactorio, sin mencionar que es sensible a los cambios futuros en el formato de archivo como resultado de romper la abstracción. Iteratos/Enumeradores vienen a la mente como una opción atractiva aquí. Busqué una biblioteca que los combinara con una serialización binaria, pero no encontré nada. Alguien sabe si esto ya se ha hecho? Si no, ¿sería útil una biblioteca para esto? ¿O me estoy perdiendo algo?

Answer 1

Así que digo, quédate con Data.Binary pero escribe una nueva instancia para las listas de crecimiento. Aquí está la corriente (estricto) ejemplo:

instance Binary a => Binary [a] where 
    put l = put (length l) >> mapM_ put l 
    get = do n <- get :: Get Int 
       getMany n 

-- | 'getMany n' get 'n' elements in order, without blowing the stack. 
getMany :: Binary a => Int -> Get [a] 
getMany n = go [] n 
where 
    go xs 0 = return $! reverse xs 
    go xs i = do x <- get 
       x `seq` go (x:xs) (i-1) 
{-# INLINE getMany #-} 

Ahora, una versión que le permite transmitir (en binario) para anexar un archivo tendría que ser ansiosos o perezoso. La versión perezosa es la más trivial. Algo así como:

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) 

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

Dado masajes apropiadamente trabaja para la transmisión. Ahora, para manejar adjuntar silenciosamente, necesitaremos poder buscar hasta el final del archivo y sobrescribir la etiqueta final 0, antes de agregar más elementos.

Answer 2

Han pasado cuatro años desde que se respondió esta pregunta, pero tuve los mismos problemas que gatoatigrado en el comentario a la respuesta de Don Stewart. El método put funciona según lo anunciado, pero get lee toda la entrada. Creo que el problema radica en la coincidencia de patrón en la declaración de caso, Stream xs <- get, que debe determinar si el get restante es Stream a o no antes de regresar.

Mi solución utiliza el ejemplo de la Data.Binary.Get como punto de partida:

import Data.ByteString.Lazy(toChunks,ByteString) 
import Data.Binary(Binary(..),getWord8) 
import Data.Binary.Get(pushChunk,Decoder(..),runGetIncremental) 
import Data.List(unfoldr) 

decodes :: Binary a => ByteString -> [a] 
decodes = runGets (getWord8 >> get) 

runGets :: Get a -> ByteString -> [a] 
runGets g = unfoldr (decode1 d) . toChunks 
    where d = runGetIncremental g 

decode1 _ [] = Nothing 
decode1 d (x:xs) = case d `pushChunk` x of 
        Fail _ _ str -> error str 
        Done x' _ a -> Just (a,x':xs) 
        k@(Partial _) -> decode1 k xs 

Nota el uso de getWord8 Esto es para leer la codificada [] y : resultante de la definición de put para la corriente de ejemplo. También tenga en cuenta que, dado que getWord8 ignora los símbolos [] y: codificados, esta implementación no detectará el final de la lista. Mi archivo codificado era solo una lista, así que funciona para eso, pero de lo contrario necesitarás modificarlo.

En cualquier caso, este decodes funcionó en memoria constante en ambos casos de acceso al cabezal y últimos elementos.