AVL trees for Data.Map and Data.Set

[Adrian Hey]

On Wednesday 01 Mar 2006 4:01 pm, Christian Maeder wrote:
> Adrian Hey wrote:
> > What were your keys, btw?
>
> data ShATerm = ShAAppl String [Int] [Int]
>
>               | ShAList [Int]        [Int]
>               | ShAInt  Integer      [Int]
>
>                 deriving (Eq, Ord)
>
> (where the last list is always empty)
>
> and something (with short strings) like:
>
>    data Id = Id [String] [Id]

I think this sort of thing is good illustration of why I don't
think the indirection overhead of implementing Maps as AVL
trees of association pairs will matter much in practice.
Chances are that it will only be used in circumstances where
indirection cost is trivial compared to comparison costs.
There's also a small saving in heap burn rate too (1 less
field per tree node).

It also illustrates why I'm now quite sceptical about the use
of any balanced tree implementation of sets and maps. It
should only really be used as a default first implementation of
JPB's API which will work for any instance of Ord, but it will
never be very efficient for non-trivial Key types IMO.

I think what we should be aiming for in the long term is
automatically derived Generalised Tries (as discussed
recently).

Regards
--
Adrian Hey