A single general modification function for Map and IntMap proposal

[Nikita Volkov]

There is a list of problems with the current "Map" and "IntMap" modification interfaces:

   - they are filled with quirky and too specialized functions

   - they are not consistent in terms of how equally named functions behave: http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-IntMap-Strict.html#v:updateLookupWithKey

   - they still don't cover some important scenarios of use

Because of the above I have very often found myself in requirement for the following function:

   withItem ::
     (Ord k) =>
     k ->
     (Maybe i -> (r, Maybe i)) ->
     Map k i -> (r, Map k i)
   withItem k f m = 
     let
       item = Map.lookup k m
       (r, item') = f item
       m' = Map.update (const item') k m
     in (r, m')

It covers all the imaginable scenarios of modification operations: delete, update, replace, - yet it also provides one with ability to extract the modified data and not only. The problem is that this implementation involves a repeated lookup for the same item: first with "lookup", then with "update" - but the "containers" library exposes no functionality to get around that. So I suggest to implement an efficient version of "withItem" in the library.

This function turns out to be far more generalized than any of the currently present in the library, so it can become a basic building block for all sorts of modifying functions, including all the already existing ones, e.g.:

   alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
   alter f k = snd . withItem k (\i -> ((), f i))

   delete :: Ord k => k -> Map k a -> Map k a
   delete k = snd . withItem k (const ((), Nothing))

   updateLookupWithKey :: 
     (Ord k) => 
     (k -> a -> Maybe a) -> 
     k -> 
     Map k a -> (Maybe a, Map k a)
   updateLookupWithKey f k = 
     withItem k $ \i -> case i of
       Just i -> case f k i of
         Nothing -> (Just i, Nothing)
         Just i' -> (Just i', Just i')
       _ -> (Nothing, Nothing)

You can see how easy it makes to achieve any sort of specialized functionality. So, besides the evident benefits, this function can also become a replacement for a whole list of confusing specialized ones, thus greatly lightening the library.

You might have also noticed how this function is based around the standard "a -> (b, a)" pattern of the "State" monad, thus making it easily composable with it using the "state" and "runState" functions.

Summarizing, my suggestions are:

   1. Implement an efficient version of "withItem" for lazy and strict versions of "Map" and "IntMap".

   2. Change the order of parameters from "lambda -> key" to "key -> lambda". The "updateLookupWithKey" example implementation shows how this change can be benefitial.

   3. Begin the deprecation process of the following functions: insertWith, insertWithKey, insertLookupWithKey, adjust, adjustWithKey, update, updateWithKey, updateLookupWithKey, alter.

A deadline for discussion is set to 6 weeks.

For a formatted version of this message please visit https://github.com/haskell/containers/issues/28.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130430/8cc48807/attachment.htm>