On 18.09 01:23, Josef Svenningsson wrote: > On 9/17/06, Jan-Willem Maessen <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
