开发者

Does there exist a monad instance for Data.Map / Data.IntMap?

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 l开发者_Go百科ittle 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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜