sequencing data structures

Iavor Diatchki
Tue, 19 Aug 2003 10:24:30 -0700


there were a lot of discussions on the library mailing list about 
deriving binary, which is related to what you are asking.  i don't think 
that dealt with cyclic datatypes though.   i don't think you can do much 
about that from within haskell, unless you somehow encoded the sharing 
explicitly in the datastructure (by adding node identifiers or something).


Martin Norbäck wrote:
> I want to sequence data structures in an efficient manner, to store them
> to files and to send them over the network.
> Simply deriving Show and Read is not very good, because it's space
> inefficient and read cannot give any output until the whole data
> structure is parsed.
> So I thought I should store them in some space efficient format.
> First problem: how to make them derivable (so that I don't have to write
> boilerplate class instances for all my data structures).
> I read the "derivable type classes" paper, but it's not implemented in
> ghc (only Unit and :+: and :*: are, which is not enough).
> So how to go about it? Using DrIFT? Template Haskell?
> Second problem: how should such a format look like?
> Ideally, I want to be able to write an infinite data structure (at least
> one containing loops). If that is not possible I want to be able to read
> as lazily as possible, this means traversing the data structure in
> breadth first order, so that a cons form can be reached quickly.
> Does anyone have any thoughts/pointers on this subject? It would
> surprise me if nobody has had this problem before.
> Regards,
> 	Martin

| Iavor S. Diatchki, Ph.D. student               |
| Department of Computer Science and Engineering |
| School of OGI at OHSU                          |
|               |