Interesting. Thanks for the feedback. You were referring to Stephen Blackheath's BerkeleyDB package? http://hackage.haskell.org/cgi-bin/hackage-scripts/package/BerkeleyDB -- Don gtener:

Thank both of you for your responses. Unfortunately I decided to switch to Python for this project, as I plan to use BerkeleyDB and Haskell bindings for it are poorly written.

Best regards

Christopher Skrzętnicki

2009/5/3 Don Stewart :

...

gtener:

...

Hi

I'm looking for a data structure with following characteristics: 1. O(1) lookup 2. O(1) modification 3. amortized O(1) append 4. O(1) size query

This roughly characterizes C++ vector<> class. I'm ready to implement it myself, but first I would like to ask if anyone knows package with similar data structure. If there are many, which one would you choose and why?

A number of the array packages behave like this.  The trie packages are O(log(wordsize)), so another option (they tend to have better append complexity as well).

-- Don