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

[Jan-Willem Maessen]

On Mon, Feb 21, 2011 at 8:07 AM, Felipe Almeida Lessa
<felipe.lessa at gmail.com> wrote:
> On Mon, Feb 21, 2011 at 12:58 PM, Max Cantor <mxcantor at gmail.com> 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