Re: [Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library

On Mon, Feb 21, 2011 at 8:07 AM, Felipe Almeida Lessa wrote:

On Mon, Feb 21, 2011 at 12:58 PM, Max Cantor wrote:

...

If you want to use the library and need a short term fix, just write a small wrapper type/module

newtype SizedMap = SizedMap (Int, HashMap) and track the size yourself.  only complication is that on inserts and deletes you'll need to check if the key existed.  other than that, it shouldn't be too difficult.

This way, the library stays super optimized but, if you need, you can track the size. As Johan said, it would slow down insert and delete a bit.  shouldn't affect lookup though..

This isn't sufficient in all cases.  How would you know the resulting size of a union or intersection?

Note that the library does not at present support union or intersection! There are various ways to deal with the problem without caching sizes at nodes, one of which is to count overlap during union or intersection operations (since this involves counting leaves that are visited during these operations). -Jan-Willem Maessen