CODEWITHSUNDEEP
haskellbinarybytestringrecursive-datastructures
Lanbo
Lanbo

Reputation: 15682

How to store recursive datatype with Data.Binary

Data.Binary is great. There is just one question I have. Let's imagine I've got a datatype like this:

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

It's easily to see that this is a recursive datatype, which works because Haskell is lazy. Since Haskell as a language uses neither references nor pointers, but presents the data as-is, I am not sure how this is going to be saved. I have the strong indication that this naive reproach will lead to an infinite bytestring...

So how can this type be safely saved?

Upvotes: 5

Views: 245

Answers (1)

augustss
augustss

Reputation: 23014

If your data has no cycles you'll be fine. But a cycle, like

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

is indeed going to generate an infinite result. The only way around this is for you to give unique labels to all nodes and use those to avoid cycles when converting to binary.

Upvotes: 6

Related Questions