[Haskell-cafe] Re: Libraries need a new owner

Adrian Hey ahey at iee.org
Tue Mar 25 12:45:58 EDT 2008

Don Stewart wrote:
> ahey:
>> Hello Folks,
>> As some of you will be aware, I have been working on various Map
>> implementations that currently live here..
>> http://code.haskell.org/collections/collections-ghc6.8
>> 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 :-)
>> Thanks
> How about we propose this work be done for Summer of Code.
> I've created a ticket here:
>     http://hackage.haskell.org/trac/summer-of-code/ticket/1549
> 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?

Hello Don,

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
    boring :-(
    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

Adrian Hey

More information about the Haskell-Cafe mailing list