ahey:
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 :-)
I was more putting it in as a stub for you to round out to a full SoC proposal to work on data structure things.. :)
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 implementations).
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 this.
Great! Would you like to revise the Soc ticket, with this information? Getting some usable generalised tries available would be a great result. -- Don