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