Improving containers library

Heinrich Apfelmus apfelmus at quantentunnel.de
Thu Mar 4 09:40:56 EST 2010


Ross Paterson wrote:
> On Wed, Mar 03, 2010 at 03:23:01PM +0100, Milan Straka wrote:
>> I have started an internship in Cambridge and will spend 3 months on
>> Haskell. One of the possible projects is improving the containers
>> library. Things I am thinking about:
>> - measuring the performance of existing implementations (notably Map and
>>   Set) and possibly improve them (either without or with API changes),
>> - adding Queue and a PriorityQueue,
>> - maybe adding a generalized trie,
>> - maybe adding a hashtable (more like a trie of the hashes, something in
>>   the line of Ideal hash trees; and maybe a 'classic' hash modifiable in
>>   the ST monad?)
> 
> Data.Sequence already provides a queue.  A Banker's queue would be a
> little faster, but IMO the difference isn't enough to justify the special
> case.  The two-stack implementation would be faster, but it performs
> poorly in a persistent setting, so fails the "general purpose" criterion.

How about the real time version of the banker's queue? That would be a
definite improvement upon  Data.Sequence  , at least.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com



More information about the Libraries mailing list