Как сохранить рекурсивный тип данных с помощью Data.Binary

Data.Binary отлично. У меня есть только один вопрос. Давайте представим, что у меня есть такой тип данных:

import Data.Binary

data Ref = Ref {
    refName :: String,
    refRefs :: [(String, Ref)]
}

instance Binary Ref where
    put a = put (refName a) >> put (refRefs a)
    get = liftM2 Ref get get

Легко видеть, что это рекурсивный тип данных, который работает, потому что Haskell ленив. Поскольку язык Haskell не использует ни ссылок, ни указателей, а представляет данные как есть, я не уверен, как это можно сохранить. У меня есть веские основания полагать, что этот наивный упрек приведет к бесконечной строке байтов...

Так как же можно безопасно сохранить этот тип?


binary haskell recursive-datastructures bytestring
person Lanbo    schedule 26.06.2011    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Если в ваших данных нет циклов, все будет в порядке. Но цикл вроде

r = Ref "a" [("b", r)]

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

person augustss    schedule 26.06.2011
comment
Так ты имеешь в виду, например, в реляционной базе данных? - person Lanbo; 26.06.2011
comment
Я имею в виду, что каждый узел должен иметь какое-то уникальное имя. Может быть, refName уникально? Затем, когда вы выводите узел, вы запоминаете его имя, поэтому, если вы когда-нибудь попытаетесь вывести этот узел снова, вы вместо этого выведете (обратную) ссылку на него. Это более сложно, но необходимо для обработки циклов. - person augustss; 26.06.2011