Dmitry Antonyuk (lomeo) wrote,
Dmitry Antonyuk
lomeo

Сериализация взаимно-рекурсивных данных

На RSDN Tonal- задаёт вопрос о сериализации взаимно-рекурсивных данных.

Очевидно, что при сериализации рекурсивных данных необходимо не сериализовать уже сериализованные данные, дабы избежать цикла. Для этого в том месте, где имеется связь со следующим рекурсивным звеном, можно сохранить ссылку.

Поэтому в голову приходит замечательный пакет data-reify от Andy Gill. О его применении можно прочитать в статье Type-Safe Observable Sharing in Haskell.

Смысл в том, что мы можем разложить рекурсивные данные на нерекурсивные данные со ссылками - то, что нам и нужно.

Т.е. для типов из примера Tonal-
data A = A {a_unuqId :: Int, a_refs :: [B]}
data B = B {b_unuqId :: Int, b_refs :: [A]}

это будет
data N u = AN { an_uniqId :: Int, an_refs :: [u] }
         | BN { bn_uniqId :: Int, bn_refs :: [u] }

Обратите внимание на дырки `u', оставленные для рекурсии - по сути A ~ N B и наоборот.
Пишем instance для MuRef
instance MuRef A where
    type DeRef A = N
    mapDeRef f (A i rs) = AN i <$> sequenceA (map f rs)

instance MuRef B where
    type DeRef B = N
    mapDeRef f (B i rs) = BN i <$> sequenceA (map f rs)

и получаем нужный граф, например
> let { a = A 1 [b] ; b = B 2 [a] }
> reifyGraph a
let [(1,AN {an_uniqId = 1, an_refs = [2]}),(2,BN {bn_uniqId = 2, bn_refs = [1]})] in 1

или
> let { a1 = A 1 [b1, b2] ; a2 = A 2 [b2] ; b1 = B 3 [a1] ; b2 = B 4 [a1, a2] }
> reifyGraph a1
let [(1,AN {an_uniqId = 1, an_refs = [2,3]}),
     (3,BN {bn_uniqId = 4, bn_refs = [1,4]}),
     (4,AN {an_uniqId = 2, an_refs = [3]}),
     (2,BN {bn_uniqId = 3, bn_refs = [1]})] in 1

Меня здесь смущает тип [(Unique, g Unique)], всё таки хочется IntMap (g Unique) - быстрее и десериализация будет проще. Впрочем, переписать библиотеку должно быть несложно.

При десериализации придётся обращать граф в конкретный тип, например, A. Это дополнительные телодвижения, но зато весь код у нас более общий и не привязан конкретно к сериализации. Например, необходимо использовать мемоизацию:
graphToA :: Graph (DeRef A) -> A
graphToA (Graph gs i) = ma ! i
    where
        ma = fromList [ (i, A ai $ map (mb!) rs) | (i, AN ai rs) <- gs ]
        mb = fromList [ (i, B bi $ map (ma!) rs) | (i, BN bi rs) <- gs ]


Покритикуйте.
Tags: fp, haskell
Subscribe
Comments for this post were disabled by the author