Efficent lens operation for Data.Map et al.
roconnor at theorem.ca
roconnor at theorem.ca
Tue Jan 17 20:22:17 CET 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.
--
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.''
More information about the Libraries
mailing list