Haskell O (n) (или ближайший) способ «изменить» значения в Data.Map

Question

Мне нужно применить функцию к каждому элементу на моей карте. Эта функция может привести к новому значению или привести к отсутствию значения, и поэтому я хотел бы, чтобы эта пара ключей/значений удалялась с моей карты. В условиях неспециалиста моя карта со временем будет уменьшаться.

Мне нравится звук функции alter в Data.Map, однако для этого нужны ключи. Поэтому мой инстинкт говорит, чтобы просто взять ключи с keys и приготовить foldl' с моей картой в качестве аккумулятора и ключами в качестве моего списка ввода.

Но разве это эффективный способ сделать это? В моем императивном сознании я делаю проход O (n), чтобы захватить ключи, а затем мой foldl 'будет работать в O (nlogn) time (log n, чтобы искать каждый пункт раз n элементов). Поэтому, в первую очередь, похоже, что это будет 2 прохода, когда потребуется только один. Я начинаю понимать, что на самом деле, ленивость Haskell заставит эти две операции работать в тандеме (то есть получить следующее значение ключа, а затем вызвать с ним изменение), так что, возможно, это не так уж плохо. Но я предпочел бы найти способ сделать это в O (n), а не O (nlogn). Очевидно, что излишним придется «искать» каждый элемент индивидуально, когда мне нужно прикоснуться ко всем им, и порядок не имеет значения в моем случае.

В качестве альтернативы, я полагаю, я мог бы копировать значения в новую карту и оставлять те, которые мне не нужны, но я бы предположил, что просто будет использовать больше памяти и победить всю цель моей сокращающейся карты.

Итак, я ищу несколько советов о том, как я могу эффективно настроить свою карту.

Примечание. Эта карта уже является аккумулятором в складке '.

Другими словами, я хочу сделать Data.Map.map, но уметь удалять значения. В настоящее время я делаю карту и фильтр, и я пытаюсь ускорить это.

Answer 1

Вы, вероятно, хотите mapMaybeWithKey функцию:

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

O (N). Сопоставьте ключи/значения и получите результаты Just.

или просто mapMaybe, если вам не нужен доступ к ключам.