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

[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 ]

Покритикуйте.

Comments

[migmit.vox.com (from livejournal.com)]

Мне не слишком нравится сваливание всех типов в один. Если у них будут по нескольку конструкторов - станет messy. Not terribly, но всё же.

Надо будет подумать, как это получше написать.

[lomeo.livejournal.com]

Меня это тоже смутило. Но я не нашёл, как выкрутиться, DeRef у них, похоже должен быть общим :(

[migmit.vox.com (from livejournal.com)]

Хотя бы разнести, чтобы они не перемешивались:

data N :: * -> * -> * where
    N_A :: Int -> [u] -> N A u
    N_B :: Int -> [u] -> N B u