Replace keys in Data.Map

Question

If I have two keys k0 and k1, which are in the Data.Map M, how can I remove k0 from the map and replace k1 with k0?

What would be the best approach to complete this task? I have tried to go through the documentation of Data.Map, but I have only been able to find functions which can change values.

Answer 1

As far as I can see, there is no single library function which can perform this for you efficiently. However, you can roll your own doing something like this:

case M.lookup k0 myMap of
   Nothing -> myMap
   Just e  -> M.insert k1 e (M.delete k0 myMap)

This will require three map operations, costing O(log N) each.

We can do it in two operations as follows:

case updateLookupWithKey (\_ _ -> Nothing) k0 myMap of
   (Nothing, _    ) -> myMap
   (Just e, newMap) -> M.insert k1 e newMap

I don't think this can be further improved, since when dealing with two distinct keys we need to access twice the underlying balanced search tree anyway.