Libraries need a new owner
ahey at iee.org
Tue Mar 25 12:45:58 EDT 2008
Don Stewart wrote:
>> Hello Folks,
>> As some of you will be aware, I have been working on various Map
>> implementations that currently live here..
>> The libs in question being Data.Tree.AVL, Data.Trie.General and a few
>> other bits like Data.COrdering and the AVL based Data.Map/Set clones.
>> Well, I have decided to stop work on these. So they need a new owner if
>> they're going to go anywhere. If anyone is interested in the job then I
>> suggest they contact myself or Jean-Philippe Bernardy.
>> Of course I will be happy to provide any help or advise anyone who takes
>> over these libs may feel they need from me. I might even contribute a
>> few patches from time to time myself :-)
> How about we propose this work be done for Summer of Code.
> I've created a ticket here:
> Add comments, or if you can mentor, add that information too!
> Let's get a new faster Data.Map and other containers ready to go by the
> end of the northern summer?
I'm not sure what you're proposing as the SOC project, but I don't think
getting AVL based Data.Map/Set clones in Hackage is particularly
suitable or challenging. This work is 99% done and also quite boring.
It could be finished by the end of today if I set my mind to it :-)
There are 3 significant things that really need doing IMO.
1- Try to reconcile the apparent differences between the collections
package and Edison class APIs. I don't really understand either
myself, but having multiple classes for "the same" things makes
both implementors and test suite writers lives harder.
The generalised trie class "GT" should still be kept separate as
it needs some weird class methods in order to make new instances
from old and can't really be finalised until this type families
stuff is available anyway.
2- Write a polymorphic test and benchmarking suite for sets, maps,
sequences etc. This would be really useful and is something that
could reasonably be done as SOC project. But it may also be little
This could be based on classes defined as a result of 1 (above),
or failing that the author would have to define yet another set
of class APIs for test/benchmarking only. This may be the simpler
approach as it doesn't assume anything about Edison or collections
abstractions (it's just a way of testing concrete data structure
3- Produce some way of automatically deriving (efficient) generalised
trie (GT) instances for user defined types. The API is huge and
complex (and likely to get bigger still), so hand writing instances
really isn't realistic in the long run.
But this may be a bit premature for SOC as the GT class API itself
is not yet complete or stable, and probably won't be until type
families are available (and tested and documented and someone
takes the trouble to finish it).
So maybe this is something for next years SOC?
That said, I know that type families are provisionally available, so
maybe doing something with generalised tries might be possible.
I don't mind mentoring anyone who wants to do something with any of
More information about the Libraries