Improving containers library

Heinrich Apfelmus apfelmus at
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.

Heinrich Apfelmus


More information about the Libraries mailing list