Serializing persistent/functional data structures

Question

Persistent data structures depend on the sharing of structure for efficiency. For an example, see here.

How can I preserve the structure sharing when I serialize the data structures and write them to a file or database? If I just naively traverse the datastructures, I'll store the correct values, but I'll lose the structure sharing. I'd like to be able to save data-structures with shared components to a file, restore them, and still have most of the structure shared in the restored data.

Answer 1

You want some form of hash-consing. This problem has been well studied. Andrew Kennedy's paper on pickler combinators explains in detail how to serialize and unserialize while preserving sharing.