Data.Map/Data.IntMap additional features

[Evan Laforge]

On Tue, Nov 3, 2009 at 6:00 PM, Louis Wasserman
<wasserman.louis at gmail.com> wrote:
>> but if it were a choice between findMax and
>> extractWithKey with some Applicative and Monoid and whatever else
>> magic, I'd use findMax every time :) I'd be wary of putting anything
>> difficult to describe in a default interface for a basic data type.
>
> Okay, some restatement required here: I'm suggesting this method only for
> Data.Map and Data.IntMap -- not for anything more common -- and I'm not by
> any means suggesting that I'd use this in every case over findMin, but
> merely using findMin as an example application.  I do think it's okay for a
> commonly used module to have some advanced methods for advanced users.

Sure, that's totally reasonable.

> In the list of methods you named as particularly critical, you talked about
> creating, inserting, updating, and deleting; you actually didn't mention
> looking up values, which I assume you meant to -- since what's the point of
> the map if you can't look up any values?  extractWithKey is useful when I
> want to look up a value, and edit it, at the same time, without an exra
> O(log n) pass, and it specifically and elegantly takes care of the case
> where we want to simultaneously look up and edit the minimum or maximum
> value of a map.

Well ok I'm sold then, sign me up :)

One other thing I haven't seen much reference too that I think could
be a big win, and that's unboxed maps.  A map in the vein of
storablevector than can pack together a lot of elements in chunks, but
keep persistence and log lookup with some shallow tree structure could
be quite handy.  I've heard clojure's arrays and maps are constructed
along these lines.