mapM for both keys and values of Data.Map
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)