Haskell Data.Map 同时查找和删除

Question

我最近在 State Monad 中使用 Data.Map 中的 Map 类型，所以我想编写一个函数，它在 Map 中查找值并将其从 Map 中删除在 State Monad 里面。我当前的实现如下所示：

lookupDelete :: (Ord k) => k -> State (Map k v) (Maybe v)
lookupDelete k = do
    m <- get
    put (M.delete k m)
    return $ M.lookup k m

虽然这有效，但感觉效率很低。对于命令式语言中的可变映射，经常会发现 delete 函数，也 return 被删除的值。我找不到这个功能，所以如果有人知道（或者可以解释为什么有 none）

，我将不胜感激

Answer 1

没有专门针对“删除和查找”的功能。相反，您使用更通用的工具：updateLookupWithKey 是“查找和更新”，其中更新可以是删除或修改。

updateLookupWithKey :: Ord k => 
  (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)

lookupDelete k = do
  (ret, m) <- gets $ updateLookupWithKey (\_ _ -> Nothing) k
  put m
  pure ret

Answer 2

一个简单的实现是 alterF:

lookupDelete :: Ord k => k -> State (Map k v) (Maybe v)
lookupDelete = state . alterF (\x -> (x, Nothing))

alterF 参数中的 x 是存储在给定 lookupDelete 的键中的 Maybe 值。这个匿名函数returns一个(Maybe v, Maybe v)。 (,) (Maybe v) 是一个函子，基本上它充当一个“上下文”，通过它我们可以从 x 中保存我们想要的任何数据。在这种情况下，我们只保存整个 x。右侧元素中的 Nothing 指定我们要删除。一旦完全应用，alterF 就会给我们 (Maybe v, Map k v)，其中上下文（左侧元素）是我们保存在匿名函数中的任何内容，右侧元素是变异映射。然后我们将这个有状态操作包装在 state.

中

alterF 非常强大：只需选择正确的“上下文”仿函数，就可以从中构建许多操作。例如。 insert 和 delete 来自使用 Identity，而 lookup 来自使用 Const (Maybe v)。当我们有 alterF 时，不需要 lookupDelete 的专门函数。理解为什么 alterF 如此强大的一种方法是识别它的类型：

flip alterF k :: Functor f => (Maybe a -> f (Maybe a)) -> Map k a -> f (Map k a)

具有此模式类型的事物

SomeClass f => (a -> f b) -> s -> f t

被称为“光学”（当SomeClass为Functor时，它们被称为“透镜”），它们代表如何“寻找”和“变异”和“整理” “结构”中的“字段”，因为它们让我们专注于结构的一部分，修改它（使用函数参数），并通过上下文保存一些信息（让我们选择 f）。有关此模式的其他用途，请参阅 lens 包。（正如 alterF 的文档所指出的，它基本上是来自 lens 的 at。）

Haskell Data.Map 同时查找和删除

Haskell Data.Map lookup AND delete at the same time

lookup

dictionary

haskell