As far as I know, the most general form of a function that allows traversing and filtering is: type Filter s t a b = foall f. Applicative f => (a -> f (Maybe b)) -> s -> f t In my witherable[0] package, I defined `Witherable` as a subclass of `Traversable` to provide such operation for various containers. class T.Traversable t => Witherable t where wither :: Applicative f => (a -> f (Maybe b)) -> t a -> f (t b) ... However, the `wither` for `Map` is currently inefficient because it is defined in terms of `traverse` and `mapMaybe`, so it traverses the container twice. Efficient implementation.would have to use the hidden constructors. I would like to propose adding `traverseMaybe` and `traverseMaybeWithKey` for `Data.Map`, `Data.IntMap`, and their strict variants (I'm suggesting more conservative name because wither might sound too unusual or poetic for a standard library. I like 'wither' though). A possible implementation would be like this: traverseMaybeWithKey :: Applicative f => (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b) traverseMaybeWithKey _ Tip = pure Tip traverseMaybeWithKey f (Bin _ kx x l r) = maybe merge (link kx) <$> f kx x <*> traverseMaybeWithKey f l <*> traverseMaybeWithKey f r I think there is potential demand for this function as well as mapMaybe. [0] http://hackage.haskell.org/package/witherable