[Haskell] combining IntMaps

[Adrian Hey]

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