Data.Map / Data.IntMap中是否存在monad实例？ [英] Does there exist a monad instance for Data.Map / Data.IntMap?

问题描述

我有一个运算在IntMap上运行的算法，我认为这个算法最好是用命令表达。也就是说，我想说的是：

• 在地图中查找值X.


• 如果它符合条件，请从地图中移除此值。


• 循环直到地图中不存在更多值。

这表示为一个双行递归很不重要，但实际的算法稍微复杂一点，涉及多次查找和删除，所以我希望能够表达它在 do 表示法中。

是否存在一个标准的状态状态monad，状态由 Data.Map 或 Data.IntMap ，我可以这样做：

  do 
 insert 5 20 
（ma，mv）<  -  lookup 4 
 case mv of 
 Just v  - >删除（从ma ma）
无 - >返回（）
  

老实说，我不确定如何最好地表达这个......由于 lookup 它似乎会受益于某种 MaybeT IntMap m 堆栈或其他。

我做了一些工作，试图根据 Data.IntMap 定义我自己的状态monad，甚至可以使插入和删除工作，但在如何处理 lookup 时遇到了一些问题。大多数情况下，我觉得这可能是某人已经解决的问题，但我在Hackage上找不到它。

你想避免使用monad变压器的任何特定原因？如果你从Hackage得到MaybeT包，你可以达到你想要的效果：

  import Control.Monad 
 import Control.Monad.Maybe 
 import Control.Monad.State 
将合格的Data.Map导入为Map 
 
类型MapM kva = MaybeT（State（Map.Map kv））a 
 
 lookupM k = MaybeT $ Map.lookup k`liftM`获得
 insertM k =修改。 Map.insert k 
 deleteM k = modify $ Map.delete k 
 
 runMap m =（翻转execState）m。 runMaybeT 
 
 foo = runMap Map.empty $ do 
 insertM 5 20 
v<  -  lookupM 4 
 deleteM v 
  

当lookupM失败时，其余的计算失败。你可以在任何时候进入和退出这些单子，这样你就可以将它们隐藏在一个纯粹的函数接口下，它只是IO monad，除非在main中（并且使用不安全的函数），否则你不能从中逃脱出去。

所有你需要记住的是返回Maybe类型的任何状态动作只需提升到MaybeT构造函数。如果你想把IO状态改变为StateT。

I have an algorithm that operates on an IntMap that I feel would best be expressed imperatively. That is, I'd like to say things like:

• Look for value X in the map.
• If it matches a criteria, remove this value from the map.
• Loop until no more values exist in the map.

This would be fairly trivial to express as a two-line recursion, but the actual algorithm is a little more complex, involving several lookups and deletions, so I'd like to be able to express it in do notation.

Is there a standard "State"-like monad where the state is represented by Data.Map or Data.IntMap, where I can do something like:

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

Honestly I'm not sure how to best express this.. due to lookup it would seem to benefit from some kind of MaybeT IntMap m stack or something.

I did do a bit of work trying to define my own state monad based on Data.IntMap, even got as far as making insert and delete work, but got a little stuck with how to deal with lookup. Mostly i feel like this is probably something someone has already solved, but I can't find it on Hackage.

解决方案

Is there any particular reason you want to avoid using monad transformers? if you get the MaybeT package from Hackage you can achieve what you want like this:

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

When lookupM fails the rest of the computation fails. You can enter and escape these monads at any time so you can hide these under a pure function interface, it's only the IO monad that you not suppose to escape out of except in main (and using unsafe functions).

All you need to remember is any state action that returns Maybe type just lift into the MaybeT constructor. If you want to do IO change State to StateT.

这篇关于Data.Map / Data.IntMap中是否存在monad实例？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！