[Haskell-cafe] Traversing a graph in STM

[Einar Karttunen]

On 18.09 01:23, Josef Svenningsson wrote:
> On 9/17/06, Jan-Willem Maessen <jmaessen at alum.mit.edu> wrote:
> >You can associate a unique name with each traversal, and store a set
> >of traversals at each node (instead of a mark bit).  But this set
> >grows without bound unless you follow each traversal with a "cleaning
> >traversal" which removes a traversal tag from the set.  And you'd
> >need some way to generate the unique names.
> >
> Well, if your set implementation used weak pointers there would be no
> need for a cleaning traversal. The garbage collector will take care of
> that. The only slightly tricky thing is to keep a live pointer to the
> unique traversal name during the entire of the traversal. But I don't
> think that should be a big problem.
>

This suffers from the problem that two traversals reading the
same parts of the graph would have a good chance to make each other
retry.

I am thinking of going the StableName route. But as this happens
inside STM Data.HashTable does not help much (without using
unsafeIOToSTM and dealing with retries).

If StableNames were in Ord using Set (StableName T)
would be nice. But in the current implementation one has to resort
to IntSet Int [StableName T] which is not pretty at all.

- Einar Karttunen