Managing a collection of unique objects

[Warwick HARVEY]

Hi again,

Thanks to Henk and Tom for providing me with source code to help with my
previous problem (in particular Tom, who went and wrote a circular list
module to do almost exactly what I wanted).

The first stage of my program utilising circular lists is now written and
working fine, but when I started to move onto the next stage, I encountered
another problem.  :-)

The problem is that I want to manage a collection of these (unique) circular
lists.  Fine, I thought, just bung 'em in one of the many ADTs already
provided (in this case a map seemed most appropriate).  The problem with
sticking them in a map (or any of the other ADTs in the standard library)
is, of course, that it doesn't preserve the uniqueness of inserted objects.

The solution seems to be to create an ADT capable of managing unique
objects properly.  Something along the lines of a store would probably be
sufficient to fill most needs; one could then put the store references into
a map or some other management structure.  There seem to be two approaches
possible for preserving uniqueness in such an ADT.  One is to force the
object to be deleted from the ADT every time it is referenced.  If one
wanted the object to be continued to be managed, the updated version would
need to be re-inserted.  The other option is to disallow direct access to
managed objects, but to allow appropriate predicates to be applied to them,
with the updated object replacing the original in the data structure.  Of
course, these options aren't mutually exclusive, and both could be provided
by an implementation.

So...  Any comments on the problem or its solutions?  Can somebody with a
better understanding of unique modes and the state of the current Mercury
implementation tell me whether it would be possible to write such an ADT in
a "clean" fashion?

If so, I might give it a go myself (I want to learn more about "advanced"
modes and how to use them anyway), but to be honest, I don't really need
this problem "solved".  I expected to have a non-unique representation of
the data at some points in the program anyway (I need to do diffs against
previous versions), so I can just put that representation under management
and recreate the circular lists on the fly (rather than the other way
around).  Either way, I thought the management of unique data structures was
an interesting problem worth discussing.

				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