haskell - 替换Data.Map中的键

如果我在Data.Map M中有两个键k0和k1，如何从地图中删除k0并将k1替换为k0？

什么是完成此任务的最佳方法？我试图浏览Data.Map的文档，但是我只能找到可以更改值的函数。

最佳答案

据我所知，没有单个库函数可以有效地为您执行此操作。但是，您可以自己滚动执行以下操作：

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

这将需要三个映射操作，每个操作的成本为O（log N）。

我们可以通过以下两个操作来做到这一点：

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

我认为这无法进一步改善，因为在处理两个不同的键时，无论如何我们都需要访问两倍的基础平衡搜索树。