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) => 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) => (a1 -> m a2) -> (b1 -> m b2) -> M.Map a1 b1 -> m (M.Map a2 b2)
mapMmap kf vf m = do
    let pairsIn = M.assocs m
    pairsOut <- mapM fs pairsIn
    return $! M.fromList pairsOut
    where
        fs (k, v) = do
            newK <- kf k
            newV <- 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) => (Key t -> a -> m b) -> t a -> 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) => 
   (a1 -> m a2) -> (b1 -> m b2) -> M.Map a1 b1 -> m (M.Map a2 b2)
mapMmap kf vf = liftM M.fromList . mapM fs . M.assocs 
    where
    fs (k, v) = liftM2 (,) (kf k) (vf v)

StackExchange Code Review Q#15606, answer score: 5