Implement traverseMaybe in Data.Map, Data.IntMap, etc
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
+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
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@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/
participants (2)
-
Fumiaki Kinoshita -
John Alfred Nathanael Chee