mapM for both keys and values of Data.Map I'm writing a monadic parser instance that transforms Data.Map.Map's:

instance (Ord a, FromEDN a, FromEDN b) =&gt; FromEDN (M.Map a b) where
    parseEDNv (E.Map m) = mapMmap parseEDNv parseEDN m
    parseEDNv v = typeMismatch "Map" v


Data.Map doesn't provide it's own mapM version like Data.Vector does, so i had to write it from scratch:

mapMmap :: (Ord a2, Monad m) =&gt; (a1 -&gt; m a2) -&gt; (b1 -&gt; m b2) -&gt; M.Map a1 b1 -&gt; m (M.Map a2 b2)
mapMmap kf vf m = do
    let pairsIn = M.assocs m
    pairsOut &lt;- mapM fs pairsIn
    return $! M.fromList pairsOut
    where
        fs (k, v) = do
            newK &lt;- kf k
            newV &lt;- vf v
            return (newK, newV)


It works, but very verbose. How to trim into a more succinct INLINEable version without too much black^W monadic magic?
There is keys library which implements 

mapWithKeyM_ :: (FoldableWithKey t, Monad m) =&gt; (Key t -&gt; a -&gt; m b) -&gt; t a -&gt; m ()


and related functions for Data.Map.

There is also Data.Traversable.mapM, but it only maps over values. Mapping over both keys and values is not a mapM operation because there is Ord constraint.

If you still consider implementing your function yourself, it can be written like this:

import qualified Data.Map as M
import Control.Monad

mapMmap :: (Ord a2, Monad m) =&gt; 
   (a1 -&gt; m a2) -&gt; (b1 -&gt; m b2) -&gt; M.Map a1 b1 -&gt; m (M.Map a2 b2)
mapMmap kf vf = liftM M.fromList . mapM fs . M.assocs 
    where
    fs (k, v) = liftM2 (,) (kf k) (vf v)