Implement traverseMaybe in Data.Map, Data.IntMap, etc

[Fumiaki Kinoshita]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20160308/2c43ee6d/attachment.html>