Self-referential data structures

[Warwick HARVEY]

Hi all,

Has anybody out there played with stores (or anything else) to implement
self-referential data structures?

What I'm trying to do is (basically) a circular list.  The documentation for
stores says:

	% Stores may be used to implement cyclic data structures such as
	% circular linked lists, etc.

The problem (for me) seems to be getting the first element inserted into the
store.  My node data type includes fields for references to the previous and
next elements, but for the first element, I cannot know what these are until
I have inserted the element (since they are references to itself).

This leaves me a little stuck.

I can think of several solutions; I'd welcome any additional input from
others.

Solution 1:
Wrap the references in the nodes in the maybe type.  This way I can create a
node with prev and next unspecified, insert it, get the reference I need,
and then replace the node.  This is perhaps the least desirable solution: I
don't want to have to deal with the maybe in all other parts of the code,
since except for during the insertion of the first element, the references
will exist.  It also means I have to do a kind of "double insertion", where
I insert the element and then immediately modify it.

Solution 2:
Modify the implementation of stores to provide a dummy reference*.  This
means I can insert the node with dummy references, get the real reference,
and update the node.  This avoids messing up all my other code, but still
has the double-insertion problem.

[*I've applied this technique to the graph module in the past - it's easy
enough to do.]

Solution 3:
Modify the implementation of stores to allow you to obtain/reserve a
reference for a node before you actually insert it.

[I don't know what implementation-level implications this has...  The store
module is implemented in C.]


Does anybody have any comments on the above?  Or another solution which does
not use stores?  Or an existing implementation of a circular list kind of
structure?  :-)

[If anybody's interested in my updated graph modules, let me know: I have
directed and undirected varieties.]

				Warwick

----------------------------------------------------------------------------
Warwick Harvey                                    email: warwick at cs.mu.OZ.AU
Department of Computer Science                        phone: +61-3-9344-9171
University of Melbourne                                 fax: +61-3-9348-1184
Parkville, Victoria, AUSTRALIA 3052     web: http://www.cs.mu.OZ.AU/~warwick