On Sat, Feb 19, 2011 at 3:04 PM, Johan Tibell <johan.tibell@gmail.com> wrote:
> On Sat, Feb 19, 2011 at 11:58 AM, Louis Wasserman
> <wasserman.louis@gmail.com> wrote:
>> A couple thoughts:
>> size takes O(n).  That's just depressing.  Really.
>
> This applies to all the container types. We could support O(1) size at
> the cost of slowing down e.g lookup, insert, and delete a little bit.
> I haven't measure how much yet. Would it be worth it?

Getting a bit picky, but for the record, Data.Map and Data.Sequence
provide O(1) size, and Data.HashTable I believe stores the information
but doesn't expose it from its tiny API. That's not an argument either
way for what a HashMap should do, however :-)