Haskell Data.Map 同时查找和删除

Question

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

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函数并返回被删除的值的情况并不少见。我找不到这个功能，所以如果有人知道一个（或可以解释为什么没有），我将不胜感激

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))

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

alterF非常强大：只需选择正确的“上下文”函子，就可以从中构建出许多操作。例如insert，delete来自于使用Identity，lookup来自于使用Const (Maybe v)。lookupDelete当我们有 时，不需要专门的函数 for alterF。理解为什么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注意的文档，它基本上at来自lens.）