Efficent lens operation for Data.Map et al.

[roconnor at theorem.ca]

On Tue, 17 Jan 2012, Johan Tibell wrote:

> On Tue, Jan 17, 2012 at 11:22 AM,  <roconnor at theorem.ca> wrote:
>> In fact, every other Map update operation should be derivable from the lens
>> function.
>
> We tried this an performance was terrible (although we used a zipper.)

I don't really see what zippers have to do with this.

Here is my non-typechecked proposal for IntMap.lens adapted from 
updateLookupWithKey and alter:

lens :: Key -> IntMap a -> (Maybe a -> IntMap a, Maybe a)
lens k t
   = case t of
       Bin p m l r
         | nomatch k p m -> (\nv -> case nv of
                              Nothing -> t
                              Just x -> join k (Tip k x) p t
                            , Nothing)
         | zero k m      -> let (fl',found) = lens k l
                            in (\nv -> bin p m (fl' nv) r, found)
         | otherwise     -> let (fr',found) = lens k r
                            in (\nv -> bin p m l (fr' nv), found)
       Tip ky y
         | k==ky         -> (\nv -> case nv of
                              Just y' -> Tip ky y')
                              Nothing -> Nil
                            , Just y)
         | otherwise     -> (\nv -> case nv of
                              Just x -> join k (Tip k x) ky t
                              Nothing -> t
                            , Nothing)
       Nil -> (\nv -> case nv of
                Just x  -> Tip k x
                Nothing -> Nil
              , Nothing)

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