Efficent lens operation for Data.Map et al.

[roconnor at theorem.ca]

Using the existing interface to Data.Map it is impossible to implement 
efficent lenses for the structures.  Right now, the implementation of 
mapLens et al. in data-lens must traverse the entire structure of the map 
twice: once to do a lookup and another to do an alteration.

mapLens :: Ord k => k -> Lens (Map k v) (Maybe v)
mapLens k = Lens $ \m -> store (\mv -> case mv of
     Nothing -> Map.delete k m
     Just v' -> Map.insert k v' m
   ) (Map.lookup k m)

A native lensing operation would improve the situtation much.  Two 
operations come close already:

(1) alter comes close but doesn't return the lookup.
(2) updateLookupWithKey comes even closer, however there is no way to 
insert a new key-value pair if the key isn't already in the map.

So I propose adding a lens operation to the Data.Map (et al.) interfaces. 
Or, if you guys like warm-fuzzy names, we could call it alterLookup.

lens :: k -> Map k a -> (Maybe a -> Map k a, Maybe a)

with the specification that

snd (lens k m) = lookup k m

fst (lens k m) v = update (const v) k m

The relationship between lens and alter is

   alter f k m = let (u,v) = lens k m in u (f v)

In fact, every other Map update operation should be derivable from the 
lens function.

I'm slowly working on a patch; however I thought I'd bring it up here on 
the mailing list in case some enterprising person who is familiar with 
these libraries wants to go ahead and implement it in Data.Map, 
Data.IntMap, Data.Set and Data.IntSet.

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''