The type would be: foldlWithKeyM :: Monad m => (a -> k -> b -> m a) -> a -> Map k b -> m a I'm happy to contribute this if it would be accepted.