RE: [Haskell] combining IntMaps
Ok, it looks like I have some more reading to do. Do you know where I can find a description of the Hedge algorithm? Also, I'm pretty new here - these conversations eventually need to get moved to haskell-cafe, right? Is there any concrete guidance regarding when that should happen? The distinction between the two lists is still vague to me. -Chad -----Original Message----- From: Adrian Hey [mailto:ahey@iee.org] Sent: Wednesday, July 27, 2005 12:04 AM To: Scherrer, Chad Cc: haskell@haskell.org Subject: Re: [Haskell] combining IntMaps Hello, On Tuesday 26 Jul 2005 7:58 pm, Scherrer, Chad wrote:
Thanks! It's interesting the way your AVL tree library is set up -- there seems to be a much broader degree of functionality than that provided by Data.Set. But I'm trying to see, is there a significant difference in the fundamental data structure.
Well Data.Set is based on a different balanced tree type (weight balanced trees), similar to those used in the Adams paper. I'm also quite sceptical about the Hedge algorithm, so the AVL library doesn't use it. It uses divide and conquer, but not quite as Adams describes it. But IMO the biggest problem with Data.Set is the inflexible API. For example..
From Data.Set: union :: Ord a => Set a -> Set a -> Set a intersect :: Ord a => Set a -> Set a -> Set a
From Data.Tree.AVL: genUnion :: (e -> e -> COrdering e) -> AVL e -> AVL e -> AVL e genIntersection :: (a -> b -> COrdering c) -> AVL a -> AVL b -> AVL c
Of course there's no reason why similar functions could not be provided by Data.Set, but they're not there at present.
or is the main point that the additional functionality could not have otherwise been provided in
an efficient way without going into the guts of Data.Set?
Yes. This why producing useable libraries like this is so difficult. There's plenty of reasonable things you just can't do efficiently with Data.Set. Same is probably true of Data.Tree.AVL of course, but I'm trying to make it more complete all the time. Anyway, please try out AVL and let me know if there's anything more missing. Regards -- Adrian Hey
On Wednesday 27 Jul 2005 6:24 pm, Scherrer, Chad wrote:
Ok, it looks like I have some more reading to do. Do you know where I can find a description of the Hedge algorithm?
It's described in the Adams paper.. http://swiss.csail.mit.edu/~adams/BB/ The reason I'm sceptical about it is that (for reasons I'm not entirely clear about) it seems to need many more comparisons than divide and conquer (something Adams didn't mention in his paper IIRC). In my tests it seems to require somewhere between 3 and 5 times as many comparisons. Adams assumes that comparison is cheap and tree balancing is expensive AFAICS. This seems wrong to me. The function is polymorphic so we have no idea regarding the cost of comparison. Also (for AVL trees at least) tree construction and balancing is not particularly expensive. (Though it does require tortuously complex and incomprehensible code :-) In any case AVL union was quite a bit faster than DData.Set union (as it was at the time) last time I tested it with sets of Ints, for whatever reason.
Also, I'm pretty new here - these conversations eventually need to get moved to haskell-cafe, right? Is there any concrete guidance regarding when that should happen? The distinction between the two lists is still vague to me.
It's vague to me too :-) Though in this case the libraries list would be more appropriate I think (dunno whether or not you're subscribed to that). Regards -- Adrian Hey
participants (2)
-
Adrian Hey -
Scherrer, Chad