sequencing data structures

Bernard James POPE bjpop@cs.mu.OZ.AU
Wed, 20 Aug 2003 18:16:36 +1000 (EST)


> I want to sequence data structures in an efficient manner, to store them
> to files and to send them over the network.
> 
> 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.

Hi Martin,

If you can live with supporting only one compiler then you can get a lot of
this done via the FFI.

In buddha, my debugger for Haskell, I have to print pretty versions of
arbitrary data structures, which is in many ways similar to what you want to do.

I recently extracted the relevent code into a library for reifying:

   http://www.cs.mu.oz.au/~bjpop/code.html

It gives:

   data Graph = ...

   reify :: a -> IO Graph

   prettyGraph :: Graph -> String

Its not what you want but it might give you some ideas.

GHC has quite a nice API for its runtime environment, and it is 
straightforward to write some C code that crawls over the heap. 
If you are careful not to cause any garbage collection then you can find
cycles without much problem. 

Some issues are what to do about thunks? You could force them but they
might diverge, so it would have to be incremental.

Also your data structure might have functions inside it, which are going to
be hard no matter what you do.

Cheers,
Bernie.