haskell - Data.Map/Data.IntMap 是否存在 monad 实例？

Question

我有一个在 IntMap 上运行的算法，我觉得最好用命令式的方式表达它。也就是说，我想说的是:

在 map 中查找值 X。

如果它符合条件，则从 map 中删除该值。

循环直到 map 中不再存在值。

用两行递归表示这将是相当简单的，但实际算法稍微复杂一些，涉及多次查找和删除，所以我希望能够在 do 中表示它。符号。

是否有一个标准的类似“状态”的单子(monad)，其中状态由 Data.Map 表示或 Data.IntMap ，我可以在其中执行以下操作:

do
  insert 5 20
  (ma, mv) <- lookup 4
  case mv of
    Just v -> delete (fromJust ma)
    Nothing -> return ()

老实说，我不确定如何最好地表达这一点.. 由于 lookup它似乎受益于某种 MaybeT IntMap m堆栈什么的。

我确实做了一些工作，试图根据 Data.IntMap 定义我自己的状态单子(monad)。 , 甚至达到了 insert和 delete工作，但对如何处理 lookup 有点困惑.大多数情况下，我觉得这可能是某人已经解决的问题，但我在 Hackage 上找不到。

Answer 1

您有什么特别的原因要避免使用 monad 转换器吗？如果你从 Hackage 获得 MaybeT 包，你可以像这样实现你想要的:

import Control.Monad
import Control.Monad.Maybe
import Control.Monad.State
import qualified Data.Map as Map

type MapM k v a = MaybeT (State (Map.Map k v)) a

lookupM k = MaybeT $ Map.lookup k `liftM` get
insertM k = modify . Map.insert k
deleteM k = modify $ Map.delete k

runMap m = (flip execState) m . runMaybeT

foo = runMap Map.empty $ do
    insertM 5 20
    v <- lookupM 4
    deleteM v

当 lookupM 失败时，其余的计算将失败。您可以随时输入和转义这些 monad，因此您可以将它们隐藏在纯函数接口(interface)下，除了在 main 中(并使用不安全的函数)之外，您不希望从 IO monad 中转义。

所有你需要记住的是任何返回 Maybe 类型的状态 Action 都只是提升到 MaybeT 构造函数中。如果你想做 IO 改变 State 到 StateT。