Efficent lens operation for Data.Map et al.
Edward Z. Yang
ezyang at MIT.EDU
Tue Jan 17 20:50:16 CET 2012
+1 on the concept, although IIRC the last time something similar came
up the constant factors were kind of bad.
Excerpts from roconnor's message of Tue Jan 17 14:22:17 -0500 2012:
> Using the existing interface to Data.Map it is impossible to implement
> efficent lenses for the structures. Right now, the implementation of
> mapLens et al. in data-lens must traverse the entire structure of the map
> twice: once to do a lookup and another to do an alteration.
> mapLens :: Ord k => k -> Lens (Map k v) (Maybe v)
> mapLens k = Lens $ \m -> store (\mv -> case mv of
> Nothing -> Map.delete k m
> Just v' -> Map.insert k v' m
> ) (Map.lookup k m)
> A native lensing operation would improve the situtation much. Two
> operations come close already:
> (1) alter comes close but doesn't return the lookup.
> (2) updateLookupWithKey comes even closer, however there is no way to
> insert a new key-value pair if the key isn't already in the map.
> So I propose adding a lens operation to the Data.Map (et al.) interfaces.
> Or, if you guys like warm-fuzzy names, we could call it alterLookup.
> lens :: k -> Map k a -> (Maybe a -> Map k a, Maybe a)
> with the specification that
> snd (lens k m) = lookup k m
> fst (lens k m) v = update (const v) k m
> The relationship between lens and alter is
> alter f k m = let (u,v) = lens k m in u (f v)
> In fact, every other Map update operation should be derivable from the
> lens function.
> I'm slowly working on a patch; however I thought I'd bring it up here on
> the mailing list in case some enterprising person who is familiar with
> these libraries wants to go ahead and implement it in Data.Map,
> Data.IntMap, Data.Set and Data.IntSet.
More information about the Libraries