Make Applicative a superclass of Monad

Summary:
This includes pretty much all the changes needed to make `Applicative`
a superclass of `Monad` finally. There's mostly reshuffling in the
interests of avoid orphans and boot files, but luckily we can resolve
all of them, pretty much. The only catch was that
Alternative/MonadPlus also had to go into Prelude to avoid this.

As a result, we must update the hsc2hs and haddock submodules.

Signed-off-by: Austin Seipp <austin@well-typed.com>

Test Plan: Build things, they might not explode horribly.

Reviewers: hvr, simonmar

Subscribers: simonmar

Differential Revision: https://phabricator.haskell.org/D13

2 files changed, 53 insertions, 29 deletions

diff --git a/libraries/base/Text/ParserCombinators/ReadP.hs b/libraries/base/Text/ParserCombinators/ReadP.hs
index a0e6e22062..afdaba5fbe 100644
--- a/libraries/base/Text/ParserCombinators/ReadP.hs
+++ b/libraries/base/Text/ParserCombinators/ReadP.hs
@@ -2,6 +2,7 @@
 {-# LANGUAGE NoImplicitPrelude #-}
 {-# LANGUAGE RankNTypes #-}
 {-# LANGUAGE MagicHash #-}
+{-# LANGUAGE DeriveFunctor #-}
 
 -----------------------------------------------------------------------------
 -- |
@@ -60,20 +61,19 @@ module Text.ParserCombinators.ReadP
   chainl1,
   chainr1,
   manyTill,
-  
+
   -- * Running a parser
   ReadS,
   readP_to_S,
   readS_to_P,
-  
+
   -- * Properties
   -- $properties
   )
  where
 
-import Control.Monad( MonadPlus(..), sequence, liftM2 )
-
-import {-# SOURCE #-} GHC.Unicode ( isSpace  )
+import Control.Monad ( Alternative(empty, (<|>)), MonadPlus(..), sequence )
+import {-# SOURCE #-} GHC.Unicode ( isSpace )
 import GHC.List ( replicate, null )
 import GHC.Base
 
@@ -99,48 +99,57 @@ data P a
   | Fail
   | Result a (P a)
   | Final [(a,String)] -- invariant: list is non-empty!
+  deriving Functor
 
 -- Monad, MonadPlus
 
+instance Applicative P where
+  pure  = return
+  (<*>) = ap
+
+instance MonadPlus P where
+  mzero = empty
+  mplus = (<|>)
+
 instance Monad P where
   return x = Result x Fail
 
   (Get f)      >>= k = Get (\c -> f c >>= k)
   (Look f)     >>= k = Look (\s -> f s >>= k)
   Fail         >>= _ = Fail
-  (Result x p) >>= k = k x `mplus` (p >>= k)
+  (Result x p) >>= k = k x <|> (p >>= k)
   (Final r)    >>= k = final [ys' | (x,s) <- r, ys' <- run (k x) s]
 
   fail _ = Fail
 
-instance MonadPlus P where
-  mzero = Fail
+instance Alternative P where
+  empty = Fail
 
   -- most common case: two gets are combined
-  Get f1     `mplus` Get f2     = Get (\c -> f1 c `mplus` f2 c)
-  
+  Get f1     <|> Get f2     = Get (\c -> f1 c <|> f2 c)
+
   -- results are delivered as soon as possible
-  Result x p `mplus` q          = Result x (p `mplus` q)
-  p          `mplus` Result x q = Result x (p `mplus` q)
+  Result x p <|> q          = Result x (p <|> q)
+  p          <|> Result x q = Result x (p <|> q)
 
   -- fail disappears
-  Fail       `mplus` p          = p
-  p          `mplus` Fail       = p
+  Fail       <|> p          = p
+  p          <|> Fail       = p
 
   -- two finals are combined
   -- final + look becomes one look and one final (=optimization)
   -- final + sthg else becomes one look and one final
-  Final r    `mplus` Final t    = Final (r ++ t)
-  Final r    `mplus` Look f     = Look (\s -> Final (r ++ run (f s) s))
-  Final r    `mplus` p          = Look (\s -> Final (r ++ run p s))
-  Look f     `mplus` Final r    = Look (\s -> Final (run (f s) s ++ r))
-  p          `mplus` Final r    = Look (\s -> Final (run p s ++ r))
+  Final r    <|> Final t    = Final (r ++ t)
+  Final r    <|> Look f     = Look (\s -> Final (r ++ run (f s) s))
+  Final r    <|> p          = Look (\s -> Final (r ++ run p s))
+  Look f     <|> Final r    = Look (\s -> Final (run (f s) s ++ r))
+  p          <|> Final r    = Look (\s -> Final (run p s ++ r))
 
   -- two looks are combined (=optimization)
   -- look + sthg else floats upwards
-  Look f     `mplus` Look g     = Look (\s -> f s `mplus` g s)
-  Look f     `mplus` p          = Look (\s -> f s `mplus` p)
-  p          `mplus` Look f     = Look (\s -> p `mplus` f s)
+  Look f     <|> Look g     = Look (\s -> f s <|> g s)
+  Look f     <|> p          = Look (\s -> f s <|> p)
+  p          <|> Look f     = Look (\s -> p <|> f s)
 
 -- ---------------------------------------------------------------------------
 -- The ReadP type
@@ -152,11 +161,19 @@ newtype ReadP a = R (forall b . (a -> P b) -> P b)
 instance Functor ReadP where
   fmap h (R f) = R (\k -> f (k . h))
 
+instance Applicative ReadP where
+    pure = return
+    (<*>) = ap
+
 instance Monad ReadP where
   return x  = R (\k -> k x)
   fail _    = R (\_ -> Fail)
   R m >>= f = R (\k -> m (\a -> let R m' = f a in m' k))
 
+instance Alternative ReadP where
+    empty = mzero
+    (<|>) = mplus
+
 instance MonadPlus ReadP where
   mzero = pfail
   mplus = (+++)
@@ -195,7 +212,7 @@ pfail = R (\_ -> Fail)
 
 (+++) :: ReadP a -> ReadP a -> ReadP a
 -- ^ Symmetric choice.
-R f1 +++ R f2 = R (\k -> f1 k `mplus` f2 k)
+R f1 +++ R f2 = R (\k -> f1 k <|> f2 k)
 
 (<++) :: ReadP a -> ReadP a -> ReadP a
 -- ^ Local, exclusive, left-biased choice: If left parser
@@ -226,7 +243,7 @@ gather (R m)
   gath l (Get f)      = Get (\c -> gath (l.(c:)) (f c))
   gath _ Fail         = Fail
   gath l (Look f)     = Look (\s -> gath l (f s))
-  gath l (Result k p) = k (l []) `mplus` gath l p
+  gath l (Result k p) = k (l []) <|> gath l p
   gath _ (Final _)    = error "do not use readS_to_P in gather!"
 
 -- ---------------------------------------------------------------------------
diff --git a/libraries/base/Text/ParserCombinators/ReadPrec.hs b/libraries/base/Text/ParserCombinators/ReadPrec.hs
index 235436c4d6..7098b50531 100644
--- a/libraries/base/Text/ParserCombinators/ReadPrec.hs
+++ b/libraries/base/Text/ParserCombinators/ReadPrec.hs
@@ -16,9 +16,9 @@
 -----------------------------------------------------------------------------
 
 module Text.ParserCombinators.ReadPrec
-  ( 
+  (
   ReadPrec,
-  
+
   -- * Precedences
   Prec,
   minPrec,
@@ -61,7 +61,7 @@ import qualified Text.ParserCombinators.ReadP as ReadP
   , pfail
   )
 
-import Control.Monad( MonadPlus(..) )
+import Control.Monad( MonadPlus(..), Alternative(..) )
 import GHC.Num( Num(..) )
 import GHC.Base
 
@@ -75,17 +75,24 @@ newtype ReadPrec a = P (Prec -> ReadP a)
 instance Functor ReadPrec where
   fmap h (P f) = P (\n -> fmap h (f n))
 
+instance Applicative ReadPrec where
+    pure = return
+    (<*>) = ap
+
 instance Monad ReadPrec where
   return x  = P (\_ -> return x)
   fail s    = P (\_ -> fail s)
   P f >>= k = P (\n -> do a <- f n; let P f' = k a in f' n)
-  
+
 instance MonadPlus ReadPrec where
   mzero = pfail
   mplus = (+++)
 
+instance Alternative ReadPrec where
+    empty = mzero
+    (<|>) = mplus
+
 -- precedences
-  
 type Prec = Int
 
 minPrec :: Prec