Efficent lens operation for Data.Map et al.

[Edward Z. Yang]

+1 on the concept, although IIRC the last time something similar came
up the constant factors were kind of bad.

Edward

Excerpts from roconnor's message of Tue Jan 17 14:22:17 -0500 2012:
> 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.
>