Efficent lens operation for Data.Map et al.

[Johan Tibell]

On Tue, Jan 17, 2012 at 3:26 PM,  <roconnor at theorem.ca> 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