[Haskell] combining IntMaps

[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