On Wed, Mar 3, 2010 at 3:23 PM, Milan Straka <fox@ucw.cz> wrote:

Hi all,

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),

In case you didn't know about it already, Criterion is an excellent benchmarking library. We've been using it extensively when benchmarking the event library. You can find some example benchmarks for a priority search queue at:

http://github.com/tibbe/event/blob/master/benchmarks/PSQ.hs

- 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?)

I would be grateful for any comments, thoughts or wishes.

Something I've been thinking about lately is how a containers library using associate data types would look like. Perhaps it would be interesting to investigate that as well.

-- Johan