Why does sequenceA need Traversable?

Question

From the Typeclassopedia:

sequence :: Monad m => [m a] -> m [a]

Takes a list of computations and combines them into one computation which collects a list of their results. It is again something of a historical accident that sequence has a Monad constraint, since it can actually be implemented only in terms of Applicative.

And indeed, there is sequenceA which operates on Applicative types.

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

But wait, why does sequenceA need the Traversable constraint when it can be implemented without it?

seqA :: Applicative f => [f a] -> f [a]
seqA = foldr fx (pure [])
         where
           fx f fs = pure (:) <*> f <*> fs)

Answer 1

This is a subject that can be initially confusing because there is a lot of history and change around it, and older explanations are out of date. The history is roughly this:

1. The idea of the sequence operation dates back to the 1990s, when the Monad class was incorporated into Haskell and people first formulated generic operations for it. The signature that you quote from the Typeclassopedia reflects this: sequence :: Monad m => [m a] -> m [a]. It can work with any monad, but it is hardcoded to work on lists.
2. The Applicative class was developed during the mid-to-late 2000s; the seminal paper that everybody cites is McBride and Patterson (2008), "Applicative Programming with Effects". McBride and Patterson also note that:
   • The old monadic sequence operation can in fact be generalized to dist :: Applicative f => [f a] -> f [a]. The Monad constraint is too narrow!
   • Likewise, the old mapM function (close relative to sequence) generalizes to traverse :: Applicative f => (a -> f b) -> [a] -> f [b].
   • This can be generalized to non-list data structures by putting these operations into a Traversable class that they propose in the paper.
3. The Applicative and Traversable classes were added into the GHC base libraries, with some small changes. The dist function was named sequenceA instead, and the Foldable class joined Traversable for types that support only a subset of Traversable's requirements.
4. These classes proved extremely popular. But that shows that the original sequence :: Monad m => [m a] -> m [a] signature was wrong in hindsight.
5. So finally, fast-forward to 2015, when GHC implemented the Applicative/Monad Proposal (make Applicative a superclass of Monad) and the Foldable/Traversable Proposal, where the base libraries were revised in order to get them close to the ideal, hindsight-informed design.

The Foldable/Traversable Proposal, however, did not change the signature of sequence. I can't tell you precisely why, but the answer is going to be some obtuse detail that boils down to historical reasons, backward compatibility or something like that. But I can tell you that if we could start all over again:

1. sequence would have sequenceA's signature;
2. sequenceA would not exist independently of sequence;
3. mapM is just traverse with the wrong signature, and thus would not exist independently either.