Двоичная сериализация для списков Undefined Длина в Haskell

Я использую Data.Binary для сериализации данных в файлах. В моем приложении я постепенно добавляю элементы в эти файлы. Два самых популярных пакета сериализации, двоичные и зерновые, обе сериализуют списки как счетчики, за которыми следуют элементы списка. Из-за этого я не могу добавить свои сериализованные файлы. В настоящее время я читаю весь файл, десериализую список, добавляю в список, повторно сериализую список и записываю его обратно в файл. Однако мой набор данных становится большим, и у меня заканчивается память. Я мог бы, вероятно, разобраться в распаковке своих структур данных, чтобы получить некоторое пространство, но этот подход не масштабируется.

Одним из решений было бы спуститься и испортить формат файла, чтобы изменить начальный счет, а затем просто добавить мои элементы. Но это не очень удовлетворительно, не говоря уже о том, чтобы быть чувствительным к будущим изменениям в формате файла в результате нарушения абстракции. Iteratees/Enumerators приходят на ум как привлекательный вариант здесь. Я искал библиотеку, объединяющую их с двоичной сериализацией, но ничего не нашел. Кто-нибудь знает, если это уже сделано? Если нет, будет ли библиотека для этого полезной? Или я что-то упускаю?

Ответ 1

Итак, я говорю stick с Data.Binary, но напишу новый экземпляр для растущих списков. Здесь текущий (строгий) экземпляр:

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 #-}

Теперь версия, которая позволяет потоку (в двоичном формате) добавлять в файл, должна быть нетерпеливой или ленивой. Ленькая версия является самой тривиальной. Что-то вроде:

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))

Масс-массаж надлежащим образом работает для потоковой передачи. Теперь, чтобы обрабатывать тихое добавление, нам нужно будет искать конец файла и перезаписывать последний тег 0, прежде чем добавлять дополнительные элементы.

Ответ 2

Это четыре года с момента ответа на этот вопрос, но я столкнулся с теми же проблемами, что и gatoatigrado, в комментарии к дону Стюарту. Метод put работает так, как рекламируется, но get читает весь ввод. Я считаю, что проблема заключается в совпадении шаблонов в выражении case, Stream xs <- get, который должен определить, остается или нет оставшийся get Stream a или нет.

Мое решение использовало пример в Data.Binary.Get как отправную точку:

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)
                     [email protected](Partial _) -> decode1 k xs

Обратите внимание на использование getWord8 Это для чтения закодированных [] и :, полученных в результате определения put для экземпляра потока. Также обратите внимание, поскольку getWord8 игнорирует кодированные символы [] и: эта реализация не будет определять конец списка. Мой закодированный файл был всего лишь одним списком, поэтому он работает для этого, но в противном случае вам нужно будет изменить.

В любом случае, этот decodes работал в постоянной памяти в обоих случаях доступа к головке и последним элементам.