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

[John Alfred Nathanael Chee]

+1, I'm a fan of the functionality that witherable provides. Would it be
possible to provide benchmarks with and without using the hidden
constructors? It might make the case more compelling.

On Tue, Mar 8, 2016 at 12:43 AM, Fumiaki Kinoshita <fumiexcel at gmail.com>
wrote:

> 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
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>


-- 
Love in Jesus Christ, John Alfred Nathanael Chee
http://www.biblegateway.com/
http://web.cecs.pdx.edu/~chee/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20160310/8e3a7055/attachment-0001.html>