On Feb 1, 2008, at 9:41 AM, Alfonso Acosta wrote:
You'd probably be interested to read http://www.cs.chalmers.se/~koen/pubs/entry-asian99-lava.html
It is indeed an interesting paper (that I've read and referred to several times over the years). But it's tricky to get right in practice! And sadly, while it solves the problem of sharing (or object equivalence) it doesn't give us some sort of total order or hash key, so there's no way to efficiently associate transient mutable state uniquely with each reference we encounter. For that we need one of the other solutions discussed and rejected. This is why Data.Unique provides a pure hashUnique function. The best option I know of here to get the desired time bounds with a purely-functional abstraction is to use a splittable supply of unique labels (which can be encapsulated in a monad if we like), then use ST to associate a hash table of references with the graph nodes while traversing the graph. -Jan