7

The signature of sequence is

sequence :: Monad m => t (m a) -> m (t a)

But we can implement it as

sequence = traverse id

requiring m to be just Applicative. If monads are applicatives then why bother having this constraint on type level?

bottaio
  • 4,963
  • 3
  • 19
  • 43
  • 18
    Historical reasons. There's `sequenceA` for the modern haskellista. – luqui Apr 03 '19 at 03:43
  • 5
    More specifically: it was defined before `Applicative` was known, and later was kept because when `Applicative` was added to `base` it wasn't a superclass of `Monad` yet. – Alexey Romanov Apr 03 '19 at 05:08
  • For some reason, several functions in the past have been generalized to foldables/traversables when those were introduced, yet the previous monad-related functions (`ap`, `sequence`, ...) kept their type even when applicatives were introduced. Such changes are not backward compatible, that's true, but the other generalizations are not backwards compatible as well -- so I'm unsure about the historic reason. (Haskell changed quite a bit: e.g., in the past `Monad` was not even a subclass of `Functor`) – chi Apr 03 '19 at 11:52
  • @chi If `[]` was given a `Foldable` instance when `foldr` was generalized to `(a -> b -> b) -> b -> t a -> b`, that's not really a incompatible change, is it? When `Applicative` was introduced, monads didn't immediately become applicatives. Now that `Applicative` *is* a superclass of `Monad`, `sequence` could probably be re-typed. (That said, what's the corner case I'm missing?) – chepner Apr 03 '19 at 11:59
  • 2
    @chepner It still is incompatible, in the general case, unfortunately. For instance if `class C a where foo :: a` with `instance C [a] where foo = []`, then `length foo` compiles if `length` forces `[a]`, but if `length` only requires a foldable the code is ambiguous. (In GHCi it works only because of `ExtendedDefaultRules`) This is a contrived example, but similar ambiguities can arise in real code. – chi Apr 03 '19 at 12:07
  • I believe, but I can't find the reference right now, that there are certain (quasi-contrived? fully-contrived?) examples where `sequence` can be faster than `sequenceA`. If anybody can find that explanation (maybe due to Edward Kmett?), I think that would make a great answer. – Antal Spector-Zabusky Apr 03 '19 at 19:35
  • Related: [*what does the A stand for in sequenceA?*](https://stackoverflow.com/q/40181086/2751851) – duplode Apr 03 '19 at 21:52

1 Answers1

7

There are many functions in Haskell that are equivalent but distinct because Applicative (resp. Functor) didn’t use to be a superclass of Monad. For example:

  • return vs. pure

  • ap vs. <*>

  • liftM vs. liftA vs. fmap

  • liftM2, liftM3, &c. vs. liftA2, liftA3, &c.

  • mapM/forM vs. traverse/for

  • mapM_/forM_ vs. traverse_/for_

  • sequence vs. sequenceA

  • mzero & mplus (from MonadPlus) vs. empty & <|> (from Alternative)

The old functions with their original Monad signatures are still present, but in new code, since the Applicative–Monad Proposal (AMP) was implemented, you can always use the Applicative versions because they’re slightly more general—that is, you can always replace return with pure, but not vice versa.

Jon Purdy
  • 53,300
  • 8
  • 96
  • 166
  • Can you elaborate on "compatibility reasons"? Specifically, what would break if today, `sequence` were changed to have `sequenceA`'s type signature, for example? – Joseph Sible-Reinstate Monica Apr 05 '19 at 01:02
  • 1
    @JosephSible: You know, I may be mistaken—nothing *should* break just from changing the signatures, and there might actually be a plan to do so in the future. It was other changes that didn’t make the cut for AMP, such as moving `join` inside `Monad` and removing `return`, iirc due to issues with the role system. – Jon Purdy Apr 06 '19 at 21:51