Haskell Data.Map 查找和同时删除

Question

我最近在状态Monad中使用了Data.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函数的情况并不少见，这些函数也返回已删除的值。 我找不到这个功能，所以如果有人知道一个(或者可以解释为什么没有)，我将不胜感激

Answer 1

一个简单的实现是alterF：

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

alterF参数中的x是存储在给定lookupDelete键处的Maybe值。此匿名函数返回一个(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

被称为"光学"(当SomeClassFunctor时，它们被称为"透镜")，它们表示如何在"结构"内部"查找"、"变异"和"整理"场"，因为它们让我们专注于结构的一部分，修改它(使用 function 参数)，并通过上下文保存一些信息(通过让我们选择f)。有关此模式的其他用法，请参阅lens包。(正如alterF文档所指出的那样，它基本上是从lensat的。

Answer 2

没有专门用于"删除和查找"的功能。相反，您使用更通用的工具：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