On Tue, Apr 05, 2005 at 06:25:00PM +0100, Adrian Hey wrote:
Hello,
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.
That's a good example of an augmented tree. In augmented binary search trees there is an additional information in each node. This information should be computable from (key, value) in the node and (key, value) plus additional information from node's children. This allows to update the info on adding, deleting, balancing, etc. Probably the most known example of augmented BST is an interval tree, but there are many other applications for this technique.
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.
That's what I feared.
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 am not sure I fully understand, but if I do, it would be a nice feature.
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 :-(
Probably. The question is how convenient you can make it.
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?
Hmmm... something like: data ATree a k v -- A for Augmented class Augmentation a k v where compute :: Maybe (a, k, v) -> (k, v) -> Maybe (a, k, v) -> a empty :: ATree a k v add :: Augmentation a k v => ATree a k v -> k -> v -> ATree a k v ... lookup :: ATree a k v -> k -> Maybe (a, k, v) For some (most?) applications it would probably be necessary to have operations working directly on tree structure, like walking down the path from tree root to a particular node.
(or better still, could you supply the code :-)
Sure, next time when I'll need such trees :-) Best regards Tomasz