Data.Map, Data.Set working together

[Adrian Hey]

Hello,

On Tuesday 05 Apr 2005 12:59 pm, Tomasz Zielonka wrote:
> Have you thought about adding support for augmented AVL trees?

I'm not sure what you have in mind, but no, other than perhaps using
an unboxed Int field to hold size information too. This would make
some sequence operations (like taking leftmost n elements) O(log n),
vs. O(n) as it currently is with the AVL implementation. Unfortunately
at the moment doing this efficiently means creating a separate type
and doing a cut and paste job on an awful lot of code.

BTW, in the ghc survey I asked the ghc folk for type
specialisation to allow unboxing in polymorphic data types.
Dunno when they're going to deliver that though :-) I wonder
if I could do something like this with template Haskell?
(haven't used it at all yet and have already forgotten
everything I read about it :-(

I suspect that for randomish keys (hash codes say) a specialised
AVL implementation would outperform the patricia trees of Data.IntMap
too. This is something I'd been thinking of doing to speed up the
comparisons in situations where the elements/keys where quite complex
data structures (I.E. when comparison is a non-trivial operation).
But again, it seems like an awful lot of work to do this by hand
(though not as much as I'm asking from the ghc folk I guess :-)

In the mean time I might consider a somewhat less efficient
non-specialised implementation of these or other things.
Could you elaborate on what you'd like to see?

(or better still, could you supply the code :-)

Regards
--
Adrian Hey