Re: Efficent lens operation for Data.Map et al.

17 Jan 2012

      On Tue, 17 Jan 2012, Johan Tibell wrote:
...
On Tue, Jan 17, 2012 at 11:22 AM,   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.''

Re: Efficent lens operation for Data.Map et al.

roconnor＠theorem.ca