Generalizing “sequence” for all functors?

Question

I have this code:

fmapM :: Monad m => (a -> m b) -> (t, a) -> m (t, b)
fmapM f (id, e) = do 
  ev <- f e
  return (id, ev)

which basically applies the function to the 2nd element in the tuple and then "extracts" the monad. Since the tuple is a functor, is there a way to generalize this for all functors? I cannot think of an implementation, but the type signature should be:

fmapM :: (Monad m, Functor f) => (a -> m b) -> f a -> m f b

it would seem like the 2nd step would be a "sequence" operation, which extracts the monad from another functor (the list). But sequence is not generalized to all functors. Can you come up with a generic implementation of fmapM?

Edit: I've realized that an old version of hugs did have this function implemented. However, I can't find the code. Now, it is suggested that I use foldable/traversable to achieve the same.

Ah, I see the fmapM you mean in old Hugs, but that was just a less general version of Traversable. It's still a class with a different implementation for each type. — shachaf
(You can derive fmap -- as well as a lot of other functions -- from just traverse, but not vice versa.) — shachaf

shachaf shachaf · Accepted Answer · 2013-07-10T04:33:23

The function you're looking for is traverse, from Data.Traversable:

traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)

Note that you can't traverse any Functor -- for example, (r ->) -- so there's a separate subclass of Traversable functors. Also note that you don't need Monad -- just Applicative (this generalization is useful).

Generalizing “sequence” for all functors?

1 Answers