Data.* collections maintenance

[Adrian Hey]

Hello folks,

On Friday 21 Oct 2005 8:37 am, Jean-Philippe Bernardy wrote:
> As some demand seem to exist for the job, I volunteer to take
> over/resume maintenance of Data.Map and friends. In the hope that will
> alleviate the heavy load on the compiler maintainers :)

Well not that I'm in any way biased :-) but might I suggest that if these
libraries are going to get an API overhaul you could probably save yourself
quite a bit of work (and get a performance boost too) if you switched from
using size balanced trees (aka Adams trees ?) to using Data.Tree.AVL.

AFAICT all the problems people seem to have mentioned recently with
current Data.Set/Map APIs are already solved in Data.Tree.AVL or are
trivially self solvable e.g. you can chose whether you want left or
right biasing (AVL is uncommitted), intersection works on trees of
different element types, strictness in elements is much more fine
tuneable..

I was about to offer half finished AVL based clones of Data.Set/Map
I have written (but not published), but having just checked it seems I
must have deleted them at some point :-( I can remember implementation
was quite easy though.

The only reservation I have about this is the size function and indexing
operations would be O(n) for AVL, not O(1) or O(log n). But the only
reason size is O(1) for size balanced trees is that you pay extra for this
information everywhere else, and I'm not sure that index functions
should be supported at all in an abstracted Map API (they seem a bit
unsafe to me). Does anybody use Data.Map indexing? and why doesn't
Data.Set support this too? (just curious :-)

Also, more generally it seems impossible to have a single optimal Set/Map
implementation for all possible element or key types. IntSet/Map will
perform better for Ints, StringMap will perform better for Strings (the
latter could be generalised to ListMap I guess, or maybe even a
SequenceMap). Where would these fit in the general scheme of things?

Regards
--
Adrian Hey