Data.Map/Data.IntMap additional features

[Louis Wasserman]

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


> And of course creating, inserting, updating, and deleting.  Rarely key
> and value mapping.  Any interface that provides those 9 functions will
> satisfy all needs I can think of.  If they can all be implemented with
> extractWithKey, then great, put that in the class interface and define
> the rest with defaulting methods.
>

Quite honestly, I use key and value mapping all the time, in most
applications I need maps for, and extractWithKey generalizes (and makes more
efficient) several applications use regularly.

Here's one more example of an application that can't be done nicely or
efficiently with application of the currently existing methods:

extractMinPair :: Map k1 (Map k2 v) -> Maybe (((k1, k2), v), Map k1 (Map k2
v))
extractMinPair m = do
   ((k1, m1), m') <- minViewWithKey m
   ((k2, v), m1') <- minViewWithKey m1
   return (((k1, k2), v), if null m1' then m' else insert k1 m1' m)

(In particular, this is the extractMin implementation from the generalized
trie on keys of type (k1, k2), which motivated the method in the first
place.)

Note that in most cases, we'll need to insert m1' back into m, which is
really ugly, and definitely destroys the nicer recursive properties that I'm
looking for.  Rather, if I can extract information and modify a value from
the map with a single use of extractWithKey,

extractMinPair m = getFirst $ extractWithKey (\ k1 m1 -> fmap (\ ((k2, v),
m1') -> (((k1, k2), v), guardNull m1')) (minViewWithKey m1)) m
   where guardNull m = if null m then Nothing else Just m

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.

Louis Wasserman
wasserman.louis at gmail.com
http://profiles.google.com/wasserman.louis
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20091103/40a0149f/attachment.html