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