algorithm - Haskell O(n)(或最接近)方法到 Data.Map 中的 "alter"值

Question

我需要对 map 中的每个元素应用一个函数。此函数可能会产生新值或导致值缺失，因此我希望从我的 map 中删除此键/值对。通俗地说，我的 map 会随着时间的推移而缩小。

我喜欢 Data.Map 中的 alter 函数，但它需要提供键。所以我的直觉告诉我，只需使用 keys 获取键，然后用我的 map 作为累加器，将键作为我的输入列表来制作一个 foldl'。

但这是一种有效的方法吗？在我的命令式思维中，我正在执行 O(n) 传递以获取 key ，然后我的 foldl' 将在 O(nlogn) 时间内运行(记录 n 以查找每个项目乘以 n 项目)。所以首先，当只需要一次时，这似乎是两次通过。我开始了解到，实际上，Haskell 的惰性会使这两个操作协同工作(即，获取下一个键值，然后调用它的 alter)，所以也许这不是那么糟糕。但我宁愿找到一种在 O(n) 而不是 O(nlogn) 中执行此操作的方法。当我需要触摸所有项目时，必须单独“查找”每个项目显然有点矫枉过正，而顺序对我来说并不重要。

或者，我想我可以将值复制到一个新 map 中并留下我不想要的值，但我认为这只会使用更多内存并破坏我缩小 map 的全部目的。

所以我正在寻找一些关于如何有效地调整我的 map 的技巧。

请注意，这张 map 已经是 foldl 中的累加器了。

换句话说，我想执行 Data.Map.map 但也能够删除值。目前我正在制作 map 和过滤器，并且正在尝试加快速度。

Answer 1

您可能需要 mapMaybeWithKey功能:

mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b

O(n). Map keys/values and collect the Just results.

或者只是简单的 mapMaybe如果您不需要访问 key 。