Data.Map, Data.Set working together

[Tomasz Zielonka]

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