Haskell O(n) (or closest) way to "alter" values in a Data.Map

Question

I need to apply a function to every element in my map. This function may result in a new value or result in the absence of a value, and so I would want this key/value pair deleted from my map. In layman terms, my map will shrink in size over time.

I like the sound of the alter function in Data.Map, however it needs keys supplied to it. So my instinct says to just grab the keys with keys and cook up a foldl' with my map as the accumulator, and the keys as my input list.

But is this an efficient way to do this? In my imperative mind, I'm making an O(n) pass to grab the keys, and then my foldl' will run in O(nlogn) time (log n to look up each item times n items). So first of all, it seems like this would be 2 passes when only one is necessary. I'm starting to learn that in reality, Haskell's laziness will make these 2 operations work in tandem (that is, get the next key value, and then call alter with it) so maybe this is not so bad. But I'd rather find a way to do this in O(n) rather than O(nlogn). It's obviously overkill to have to "lookup" each item individually when I need to touch all of them, and order does not matter in my case.

Alternatively, I suppose I could copy values into a new map and leave behind the ones I don't want, but I would imagine that would simply use more memory and defeat the whole purpose of my shrinking map.

So I'm looking for some tips on how I can tweak my map efficiently.

Note, this map is already the accumulator in a foldl'.

In other words, I want to do Data.Map.map but be able to remove values as well. Currently I'm doing a map and a filter and I'm trying to speed this up.

Answer 1

You probably want the mapMaybeWithKey function:

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

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

or just plain mapMaybe if you don't need access to the keys.