haskell - 替换 Data.Map 中的键

Question

如果我有两个键 k0 和 k1，它们位于 Data.Map M 中，如何从 map 中删除 k0 并将 k1 替换为 k0？

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

Answer 1

据我所知，没有任何一个库函数可以有效地为您执行此操作。但是，您可以自己做这样的事情:

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

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