[Haskell-cafe] fast graph algorithms without object identities

[Jan-Willem Maessen]

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