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

On Tue, Jan 17, 2012 at 3:26 PM, wrote:

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

It's another way of creating a continuation by saving the stack.

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)

Try it out on the Criterion benchmarks in the source repo. I'd be curious to see the results. -- Johan