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

Question

我有一个在IntMap上运行的算法,我觉得最好用强制表达.也就是说,我想说的话:

• 在地图中查找值X.
• 如果它符合条件,请从地图中删除此值.
• 循环,直到地图中不再存在值.

这表示为两行递归是相当微不足道的,但实际算法稍微复杂一些,涉及多次查找和删除,所以我希望能够用do符号表达它.

是否有一个标准的"州"式单子格,其中州代表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堆栈或其他东西中受益.

我确实做了一些工作,尝试定义我自己的状态monad基于Data.IntMap,甚至得到了制作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,这样你就可以在纯函数接口下隐藏它们,它只是你不应该从主要(和使用不安全的函数)中逃脱的IO monad.

所有你需要记住的是任何状态动作,它返回Maybe类型,只是提升到MaybeT构造函数中.如果要进行IO更改状态为StateT.