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