Export `Traversable()` and `Foldable()` from Prelude

This exposes *only* the type-classes w/o any of their methods.
This is the very first step for implementing BPP (see #9586), which
already requires breaking up several import-cycles leading back to `Prelude`.

Ideally, importing `Prelude` should be avoided in most `base` modules,
as `Prelude` does not define any entities, but rather re-exports
existing ones.

Test Plan: validate passes

Reviewers: ekmett, austin

Reviewed By: ekmett, austin

Subscribers: simonmar, ezyang, carter

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

GHC Trac Issues: #9586

14 files changed, 106 insertions, 59 deletions

diff --git a/libraries/base/Control/Applicative.hs b/libraries/base/Control/Applicative.hs
index 41049c6a9f..7bab7294fb 100644
--- a/libraries/base/Control/Applicative.hs
+++ b/libraries/base/Control/Applicative.hs
@@ -1,6 +1,7 @@
-{-# LANGUAGE Trustworthy #-}
 {-# LANGUAGE AutoDeriveTypeable #-}
 {-# LANGUAGE DeriveGeneric #-}
+{-# LANGUAGE NoImplicitPrelude #-}
+{-# LANGUAGE Trustworthy #-}
 
 -----------------------------------------------------------------------------
 -- |
@@ -46,16 +47,22 @@ module Control.Applicative (
     optional,
     ) where
 
-import Prelude hiding (id,(.))
-
-import GHC.Base (liftA, liftA2, liftA3, (<**>))
 import Control.Category
 import Control.Arrow
-import Control.Monad (liftM, ap, MonadPlus(..), Alternative(..))
+import Control.Monad (liftM, ap, Monad(..), MonadPlus(..), Alternative(..))
 import Data.Functor ((<$>), (<$))
+import Data.Maybe
 import Data.Monoid (Monoid(..))
+import Data.Tuple
+import Data.Eq
+import Data.Ord
+import Data.Functor (Functor(..))
 
+import GHC.Base (const, Applicative(..),liftA, liftA2, liftA3, (<**>))
 import GHC.Generics
+import GHC.List (map, repeat, zipWith)
+import GHC.Read (Read)
+import GHC.Show (Show)
 
 newtype Const a b = Const { getConst :: a }
                   deriving (Generic, Generic1)
diff --git a/libraries/base/Control/Arrow.hs b/libraries/base/Control/Arrow.hs
index f6067a01c3..0efaa87e69 100644
--- a/libraries/base/Control/Arrow.hs
+++ b/libraries/base/Control/Arrow.hs
@@ -1,3 +1,4 @@
+{-# LANGUAGE NoImplicitPrelude #-}
 {-# LANGUAGE Trustworthy #-}
 -----------------------------------------------------------------------------
 -- |
@@ -41,11 +42,12 @@ module Control.Arrow (
     ArrowLoop(..)
     ) where
 
-import Prelude hiding (id,(.))
-
+import Data.Tuple ( fst, snd, uncurry )
+import Data.Either
 import Control.Monad
 import Control.Monad.Fix
 import Control.Category
+import GHC.Base ( Applicative(..), const, ($) )
 
 infixr 5 <+>
 infixr 3 ***
diff --git a/libraries/base/Control/Category.hs b/libraries/base/Control/Category.hs
index 3b8dc2b5ce..22166477e6 100644
--- a/libraries/base/Control/Category.hs
+++ b/libraries/base/Control/Category.hs
@@ -1,4 +1,5 @@
 {-# LANGUAGE GADTs #-}
+{-# LANGUAGE NoImplicitPrelude #-}
 {-# LANGUAGE PolyKinds #-}
 {-# LANGUAGE Trustworthy #-}
 
@@ -16,7 +17,7 @@
 
 module Control.Category where
 
-import qualified Prelude
+import qualified GHC.Base (id,(.))
 import Data.Type.Coercion
 import Data.Type.Equality
 import GHC.Prim (coerce)
@@ -43,8 +44,8 @@ class Category cat where
  #-}
 
 instance Category (->) where
-    id = Prelude.id
-    (.) = (Prelude..)
+    id = GHC.Base.id
+    (.) = (GHC.Base..)
 
 instance Category (:~:) where
   id          = Refl
diff --git a/libraries/base/Control/Monad/Fix.hs b/libraries/base/Control/Monad/Fix.hs
index 8036fefcd1..56e249c746 100644
--- a/libraries/base/Control/Monad/Fix.hs
+++ b/libraries/base/Control/Monad/Fix.hs
@@ -1,4 +1,5 @@
 {-# LANGUAGE Trustworthy #-}
+{-# LANGUAGE NoImplicitPrelude #-}
 
 -----------------------------------------------------------------------------
 -- |
@@ -22,10 +23,14 @@ module Control.Monad.Fix (
         fix
   ) where
 
-import Prelude
-import System.IO
-import Data.Function (fix)
+import Control.Monad ( Monad )
+import Data.Either
+import Data.Function ( fix )
+import Data.Maybe
+import GHC.Base ( error, (.) )
+import GHC.List ( head, tail )
 import GHC.ST
+import System.IO
 
 -- | Monads having fixed points with a \'knot-tying\' semantics.
 -- Instances of 'MonadFix' should satisfy the following laws:
diff --git a/libraries/base/Data/Data.hs b/libraries/base/Data/Data.hs
index 095bca119f..8407c6f1ba 100644
--- a/libraries/base/Data/Data.hs
+++ b/libraries/base/Data/Data.hs
@@ -2,6 +2,7 @@
 {-# LANGUAGE RankNTypes, ScopedTypeVariables, PolyKinds #-}
 {-# LANGUAGE StandaloneDeriving, AutoDeriveTypeable, TypeOperators,
              GADTs #-}
+{-# LANGUAGE NoImplicitPrelude #-}
 
 -----------------------------------------------------------------------------
 -- |
@@ -106,19 +107,25 @@ module Data.Data (
 
 ------------------------------------------------------------------------------
 
-import Prelude -- necessary to get dependencies right
-
-import Data.Typeable
+import Control.Monad
+import Data.Either
+import Data.Eq
 import Data.Maybe
+import Data.Ord
+import Data.Typeable
 import Data.Version( Version(..) )
-import Control.Monad
+import GHC.Base
+import GHC.List
+import GHC.Num
+import GHC.Read
+import GHC.Show
+import Text.Read( reads )
 
 -- Imports for the instances
 import Data.Int              -- So we can give Data instance for Int8, ...
 import Data.Type.Coercion
-import Data.Coerce
 import Data.Word             -- So we can give Data instance for Word8, ...
-import GHC.Real( Ratio(..) ) -- So we can give Data instance for Ratio
+import GHC.Real              -- So we can give Data instance for Ratio
 --import GHC.IOBase            -- So we can give Data instance for IO, Handle
 import GHC.Ptr               -- So we can give Data instance for Ptr
 import GHC.ForeignPtr        -- So we can give Data instance for ForeignPtr
diff --git a/libraries/base/Data/Foldable.hs b/libraries/base/Data/Foldable.hs
index 0f0d5bfbf1..4e6681a542 100644
--- a/libraries/base/Data/Foldable.hs
+++ b/libraries/base/Data/Foldable.hs
@@ -1,3 +1,4 @@
+{-# LANGUAGE NoImplicitPrelude #-}
 {-# LANGUAGE Trustworthy #-}
 
 -----------------------------------------------------------------------------
@@ -57,19 +58,21 @@ module Data.Foldable (
     find
     ) where
 
-import Prelude hiding (foldl, foldr, foldl1, foldr1, mapM_, sequence_,
-                elem, notElem, concat, concatMap, and, or, any, all,
-                sum, product, maximum, minimum)
-import qualified Prelude (foldl, foldr, foldl1, foldr1)
-import qualified Data.List as List (foldl')
 import Control.Applicative
-import Control.Monad (MonadPlus(..))
-import Data.Maybe (fromMaybe, listToMaybe)
+import Control.Monad ( Monad(..), MonadPlus(..) )
+import Data.Bool
+import Data.Either
+import Data.Eq
+import qualified Data.List as List
+import Data.Maybe
 import Data.Monoid
+import Data.Ord
 import Data.Proxy
 
-import GHC.Exts (build)
-import GHC.Arr
+import GHC.Arr  ( Array(..), Ix(..), elems )
+import GHC.Base ( (.), ($!), error, flip, id )
+import GHC.Exts ( build )
+import GHC.Num  ( Num(..) )
 
 -- | Data structures that can be folded.
 --
@@ -163,11 +166,11 @@ instance Foldable Maybe where
     foldl f z (Just x) = f z x
 
 instance Foldable [] where
-    foldr = Prelude.foldr
-    foldl = Prelude.foldl
+    foldr = List.foldr
+    foldl = List.foldl
     foldl' = List.foldl'
-    foldr1 = Prelude.foldr1
-    foldl1 = Prelude.foldl1
+    foldr1 = List.foldr1
+    foldl1 = List.foldl1
 
 instance Foldable (Either a) where
     foldMap _ (Left _) = mempty
@@ -182,10 +185,10 @@ instance Foldable ((,) a) where
     foldr f z (_, y) = f y z
 
 instance Ix i => Foldable (Array i) where
-    foldr f z = Prelude.foldr f z . elems
-    foldl f z = Prelude.foldl f z . elems
-    foldr1 f = Prelude.foldr1 f . elems
-    foldl1 f = Prelude.foldl1 f . elems
+    foldr f z = List.foldr f z . elems
+    foldl f z = List.foldl f z . elems
+    foldr1 f = List.foldr1 f . elems
+    foldl1 f = List.foldl1 f . elems
 
 instance Foldable Proxy where
     foldMap _ _ = mempty
diff --git a/libraries/base/Data/Function.hs b/libraries/base/Data/Function.hs
index a3fac7ca4d..81ab2224c1 100644
--- a/libraries/base/Data/Function.hs
+++ b/libraries/base/Data/Function.hs
@@ -1,4 +1,5 @@
-{-# LANGUAGE Safe #-}
+{-# LANGUAGE NoImplicitPrelude #-}
+{-# LANGUAGE Trustworthy #-}
 
 -----------------------------------------------------------------------------
 -- |
@@ -24,7 +25,7 @@ module Data.Function
   , on
   ) where
 
-import Prelude
+import GHC.Base ( ($), (.), id, const, flip )
 
 infixl 0 `on`
 infixl 1 &
diff --git a/libraries/base/Data/Functor.hs b/libraries/base/Data/Functor.hs
index 1869b1604a..f769d52446 100644
--- a/libraries/base/Data/Functor.hs
+++ b/libraries/base/Data/Functor.hs
@@ -1,3 +1,4 @@
+{-# LANGUAGE NoImplicitPrelude #-}
 {-# LANGUAGE Trustworthy #-}
 
 -----------------------------------------------------------------------------
@@ -23,7 +24,7 @@ module Data.Functor
     ) where
 
 import Control.Monad
-import GHC.Base (Functor(..))
+import GHC.Base ( Functor(..), flip )
 
 infixl 4 <$>
 
diff --git a/libraries/base/Data/Traversable.hs b/libraries/base/Data/Traversable.hs
index e69d2b3c5a..19e9d477e6 100644
--- a/libraries/base/Data/Traversable.hs
+++ b/libraries/base/Data/Traversable.hs
@@ -1,3 +1,4 @@
+{-# LANGUAGE NoImplicitPrelude #-}
 {-# LANGUAGE Trustworthy #-}
 
 -----------------------------------------------------------------------------
@@ -50,14 +51,19 @@ module Data.Traversable (
     foldMapDefault,
     ) where
 
-import Prelude hiding (mapM, sequence, foldr)
-import qualified Prelude (mapM, foldr)
 import Control.Applicative
-import Data.Foldable (Foldable())
-import Data.Monoid (Monoid)
+import Control.Monad ( Monad(..) )
+import qualified Control.Monad
+import Data.Either
+import Data.Foldable ( Foldable )
+import Data.Functor
+import Data.Maybe
+import Data.Monoid ( Monoid )
 import Data.Proxy
 
 import GHC.Arr
+import GHC.Base ( ($), (.), id, flip )
+import qualified GHC.List as List
 
 -- | Functors representing data structures that can be traversed from
 -- left to right.
@@ -174,10 +180,10 @@ instance Traversable Maybe where
 
 instance Traversable [] where
     {-# INLINE traverse #-} -- so that traverse can fuse
-    traverse f = Prelude.foldr cons_f (pure [])
+    traverse f = List.foldr cons_f (pure [])
       where cons_f x ys = (:) <$> f x <*> ys
 
-    mapM = Prelude.mapM
+    mapM = Control.Monad.mapM
 
 instance Traversable (Either a) where
     traverse _ (Left x) = pure (Left x)
diff --git a/libraries/base/Data/Version.hs b/libraries/base/Data/Version.hs
index 8b88486571..adc0f125b5 100644
--- a/libraries/base/Data/Version.hs
+++ b/libraries/base/Data/Version.hs
@@ -1,5 +1,6 @@
-{-# LANGUAGE Trustworthy #-}
 {-# LANGUAGE AutoDeriveTypeable #-}
+{-# LANGUAGE NoImplicitPrelude #-}
+{-# LANGUAGE Trustworthy #-}
 
 -----------------------------------------------------------------------------
 -- |
@@ -33,14 +34,17 @@ module Data.Version (
         showVersion, parseVersion,
   ) where
 
-import Prelude -- necessary to get dependencies right
-
-import Text.ParserCombinators.ReadP
-
-import Data.Typeable    ( Typeable )
-import Data.List        ( intersperse, sort )
-import Control.Monad    ( liftM )
+import Control.Monad    ( Monad(..), liftM )
 import Data.Char        ( isDigit, isAlphaNum )
+import Data.Eq
+import Data.List
+import Data.Ord
+import Data.Typeable    ( Typeable )
+import GHC.Base         ( ($), (&&), String, Int )
+import GHC.Read
+import GHC.Show
+import Text.ParserCombinators.ReadP
+import Text.Read        ( read )
 
 {- |
 A 'Version' represents the version of a software entity.  
diff --git a/libraries/base/Debug/Trace.hs b/libraries/base/Debug/Trace.hs
index 92e5b205c8..9705e29fdc 100644
--- a/libraries/base/Debug/Trace.hs
+++ b/libraries/base/Debug/Trace.hs
@@ -1,5 +1,7 @@
+{-# LANGUAGE MagicHash #-}
+{-# LANGUAGE NoImplicitPrelude #-}
+{-# LANGUAGE UnboxedTuples #-}
 {-# LANGUAGE Unsafe #-}
-{-# LANGUAGE MagicHash, UnboxedTuples #-}
 
 -----------------------------------------------------------------------------
 -- |
@@ -42,7 +44,6 @@ module Debug.Trace (
         traceMarkerIO,
   ) where
 
-import Prelude
 import System.IO.Unsafe
 import Control.Monad
 
@@ -51,6 +52,7 @@ import GHC.Base
 import qualified GHC.Foreign
 import GHC.IO.Encoding
 import GHC.Ptr
+import GHC.Show
 import GHC.Stack
 import Data.List
 
diff --git a/libraries/base/GHC/Exts.hs b/libraries/base/GHC/Exts.hs
index 938631001a..6499da878a 100755
--- a/libraries/base/GHC/Exts.hs
+++ b/libraries/base/GHC/Exts.hs
@@ -1,5 +1,6 @@
 {-# LANGUAGE Unsafe #-}
 {-# LANGUAGE MagicHash, UnboxedTuples, AutoDeriveTypeable, TypeFamilies, MultiParamTypeClasses, FlexibleInstances #-}
+{-# LANGUAGE NoImplicitPrelude #-}
 
 -----------------------------------------------------------------------------
 -- |
@@ -71,14 +72,13 @@ module GHC.Exts
         IsList(..)
        ) where
 
-import Prelude
-
-import GHC.Prim hiding (coerce)
+import GHC.Prim hiding (coerce, Constraint)
 import GHC.Base hiding (coerce) -- implicitly comes from GHC.Prim
 import GHC.Word
 import GHC.Int
 import GHC.Ptr
 import GHC.Stack
+
 import qualified Data.Coerce
 import Data.String
 import Data.List
diff --git a/libraries/base/GHC/Stack.hsc b/libraries/base/GHC/Stack.hsc
index 079f5b0516..0b30391cdc 100644
--- a/libraries/base/GHC/Stack.hsc
+++ b/libraries/base/GHC/Stack.hsc
@@ -13,7 +13,7 @@
 -- /Since: 4.5.0.0/
 -----------------------------------------------------------------------------
 
-{-# LANGUAGE UnboxedTuples, MagicHash #-}
+{-# LANGUAGE UnboxedTuples, MagicHash, NoImplicitPrelude #-}
 module GHC.Stack (
     -- * Call stack
     currentCallStack,
@@ -34,6 +34,8 @@ module GHC.Stack (
     renderStack
   ) where
 
+import Control.Monad ( (=<<) )
+
 import Foreign
 import Foreign.C
 
@@ -43,6 +45,7 @@ import GHC.Ptr
 import GHC.Foreign as GHC
 import GHC.IO.Encoding
 import GHC.Exception
+import GHC.List ( concatMap, null, reverse )
 
 #define PROFILING
 #include "Rts.h"
diff --git a/libraries/base/Prelude.hs b/libraries/base/Prelude.hs
index f58cd17cd2..53414c95dc 100644
--- a/libraries/base/Prelude.hs
+++ b/libraries/base/Prelude.hs
@@ -72,6 +72,9 @@ module Prelude (
     Monad((>>=), (>>), return, fail),
     mapM, mapM_, sequence, sequence_, (=<<),
 
+    -- ** Traversals and Foldables
+    Foldable, Traversable,
+
     -- ** Miscellaneous functions
     id, const, (.), flip, ($), until,
     asTypeOf, error, undefined,
@@ -140,7 +143,9 @@ import System.IO
 import System.IO.Error
 import Data.List
 import Data.Either
+import Data.Foldable    ( Foldable )
 import Data.Maybe
+import Data.Traversable ( Traversable )
 import Data.Tuple
 
 import GHC.Base