Re: [Haskell-cafe] Traversing a graph in STM

On 18.09 01:23, Josef Svenningsson wrote:

On 9/17/06, Jan-Willem Maessen 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