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

Max Cantor mxcantor at gmail.com
Mon Feb 21 13:58:45 CET 2011

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..


On Feb 20, 2011, at 11:40 AM, Louis Wasserman wrote:

> I'd like to complain about that, too ;)
> Louis Wasserman
> wasserman.louis at gmail.com
> http://profiles.google.com/wasserman.louis
> On Sat, Feb 19, 2011 at 9:02 PM, Edward Kmett <ekmett at gmail.com> wrote:
> On Sat, Feb 19, 2011 at 7:27 PM, Sterling Clover <s.clover at gmail.com> wrote:
> On Sat, Feb 19, 2011 at 3:04 PM, Johan Tibell <johan.tibell at gmail.com> wrote:
> > On Sat, Feb 19, 2011 at 11:58 AM, Louis Wasserman
> > <wasserman.louis at 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 :-)
> NB: Data.IntMap, which Data.HashMap is based on, actually only provides O(n) size.
> -Edward
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list