Traversable#mapM & sequence - Necessary?

Question

class (Functor t, Foldable t) => Traversable t where
  traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
  sequenceA :: Applicative f => t (f a) -> f (t a)
  mapM      ::       Monad m => (a -> m b) -> t a -> m (t b)
  sequence  ::       Monad m => t (m a) -> m (t a)

A good exercise is to figure out what the default implementations should be: given either traverse or sequenceA, how would you define the other three methods?

I came up with the following code that type-checks:

class (Functor t, Foldable t) => MyTraversable t where
  traverse'  :: Applicative f => (a -> f b) -> t a -> f (t b)
  traverse' = error "..."
  sequenceA' :: Applicative f => t (f a) -> f (t a)
  sequenceA' f = traverse' id f
  mapM      ::       Monad m => (a -> m b) -> t a -> m (t b)
  mapM = traverse'
  sequence'  ::       Monad m => t (m a) -> m (t a)
  sequence' = sequenceA'

If my implementations of mapM and sequence' are correct, and, since every Monad is an Applicative:

λ: :i Monad
class Applicative m => Monad (m :: * -> *) where
...

then it's not clear to me why mapM and sequence' are even necessary. Why are they?

P.S. - Credit and my thanks to haoformayor for helping me out with sequenceA.

There was an embarrassing time when not every Monad was an Applicative. — Daniel Wagner
You didn't ask about this, but you should never make a default class method that always produces an error. Just don't make a default in that case; GHC will warn if the method isn't defined in an instance. With a bogus default, users get no warning; things just blow up at runtime. — dfeuer

phadej phadej · Accepted Answer · 2015-12-28T09:51:26

As mentioned in the comments, there was a time when not every Monad was an Applicative. Just recently (in base-4.8 which shipped with GHC 7.10) the Applicative was made a superclass of Monad. You might have seen Applicative-Monad-Proposal, AMP.

Currently the Monad of no return, MRP (email-thread) is worked on, which will make Monad's >> and Applicative's *> the same. Which eventlually would make possible to say that traverse = mapM and sequence = sequenceA. But that is a long process, which will take time.

So to answer your question: for history reasons.

Traversable#mapM & sequence - Necessary?

1 Answers