10 files changed, 202 insertions, 18 deletions
diff --git a/libraries/base/Data/Coerce.hs b/libraries/base/Data/Coerce.hs
index bf269f5ea8..653a857da8 100644
--- a/libraries/base/Data/Coerce.hs
+++ b/libraries/base/Data/Coerce.hs
@@ -1,6 +1,5 @@
 {-# LANGUAGE Unsafe #-}
-{-# LANGUAGE DeriveDataTypeable #-}
-{-# LANGUAGE StandaloneDeriving #-}
+{-# LANGUAGE NoImplicitPrelude #-}
 
 -----------------------------------------------------------------------------
 -- |
@@ -26,3 +25,6 @@ module Data.Coerce
         ) where
 import GHC.Prim (coerce)
 import GHC.Types (Coercible)
+
+import GHC.Base () -- for build ordering
+
diff --git a/libraries/base/Data/Complex.hs b/libraries/base/Data/Complex.hs
index af593cda2f..0ce148788d 100644
--- a/libraries/base/Data/Complex.hs
+++ b/libraries/base/Data/Complex.hs
@@ -1,5 +1,5 @@
 {-# LANGUAGE Trustworthy #-}
-{-# LANGUAGE DeriveDataTypeable #-}
+{-# LANGUAGE AutoDeriveTypeable #-}
 {-# LANGUAGE StandaloneDeriving #-}
 
 -----------------------------------------------------------------------------
diff --git a/libraries/base/Data/Data.hs b/libraries/base/Data/Data.hs
index a12a6d7144..49407fae16 100644
--- a/libraries/base/Data/Data.hs
+++ b/libraries/base/Data/Data.hs
@@ -1,6 +1,6 @@
 {-# LANGUAGE Trustworthy, FlexibleInstances #-}
 {-# LANGUAGE RankNTypes, ScopedTypeVariables, PolyKinds #-}
-{-# LANGUAGE StandaloneDeriving, DeriveDataTypeable, TypeOperators,
+{-# LANGUAGE StandaloneDeriving, AutoDeriveTypeable, TypeOperators,
              GADTs #-}
 
 -----------------------------------------------------------------------------
@@ -323,7 +323,7 @@ class Typeable a => Data a where
 
   -- | A generic query that processes the immediate subterms and returns a list
   -- of results.  The list is given in the same order as originally specified
-  -- in the declaratoin of the data constructors.
+  -- in the declaration of the data constructors.
   gmapQ :: (forall d. Data d => d -> u) -> a -> [u]
   gmapQ f = gmapQr (:) [] f
 
@@ -777,12 +777,12 @@ mkCharConstr dt c = case datarep dt of
 
 ------------------------------------------------------------------------------
 --
---      Non-representations for non-presentable types
+--      Non-representations for non-representable types
 --
 ------------------------------------------------------------------------------
 
 
--- | Constructs a non-representation for a non-presentable type
+-- | Constructs a non-representation for a non-representable type
 mkNoRepType :: String -> DataType
 mkNoRepType str = DataType
                         { tycon   = str
diff --git a/libraries/base/Data/Dynamic.hs b/libraries/base/Data/Dynamic.hs
index 7d49a06bc3..50bea62e1a 100644
--- a/libraries/base/Data/Dynamic.hs
+++ b/libraries/base/Data/Dynamic.hs
@@ -1,6 +1,6 @@
 {-# LANGUAGE Trustworthy #-}
 {-# LANGUAGE NoImplicitPrelude #-}
-{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}
+{-# LANGUAGE AutoDeriveTypeable, StandaloneDeriving #-}
 
 -----------------------------------------------------------------------------
 -- |
diff --git a/libraries/base/Data/Either.hs b/libraries/base/Data/Either.hs
index cf45e79456..9abb20522c 100644
--- a/libraries/base/Data/Either.hs
+++ b/libraries/base/Data/Either.hs
@@ -1,6 +1,6 @@
 {-# LANGUAGE Trustworthy #-}
 {-# LANGUAGE NoImplicitPrelude #-}
-{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}
+{-# LANGUAGE AutoDeriveTypeable, StandaloneDeriving #-}
 {-# LANGUAGE PolyKinds, DataKinds, TypeFamilies, TypeOperators, UndecidableInstances #-}
 
 -----------------------------------------------------------------------------
diff --git a/libraries/base/Data/Fixed.hs b/libraries/base/Data/Fixed.hs
index f5fb896c38..cadbb61ac1 100644
--- a/libraries/base/Data/Fixed.hs
+++ b/libraries/base/Data/Fixed.hs
@@ -1,6 +1,6 @@
 {-# LANGUAGE Trustworthy #-}
 {-# LANGUAGE ScopedTypeVariables #-}
-{-# LANGUAGE DeriveDataTypeable #-}
+{-# LANGUAGE AutoDeriveTypeable #-}
 {-# OPTIONS -Wall -fno-warn-unused-binds #-}
 
 -----------------------------------------------------------------------------
@@ -158,9 +158,13 @@ instance (HasResolution a) => Read (Fixed a) where
 
 convertFixed :: forall a . HasResolution a => Lexeme -> ReadPrec (Fixed a)
 convertFixed (Number n)
- | Just (i, f) <- numberToFixed r n =
-    return (fromInteger i + (fromInteger f / (10 ^ r)))
+ | Just (i, f) <- numberToFixed e n =
+    return (fromInteger i + (fromInteger f / (10 ^ e)))
     where r = resolution (undefined :: Fixed a)
+          -- round 'e' up to help make the 'read . show == id' property
+          -- possible also for cases where 'resolution' is not a
+          -- power-of-10, such as e.g. when 'resolution = 128'
+          e = ceiling (logBase 10 (fromInteger r) :: Double)
 convertFixed _ = pfail
 
 data E0 = E0
diff --git a/libraries/base/Data/Type/Equality.hs b/libraries/base/Data/Type/Equality.hs
index 464f7d28dd..626e817b30 100644
--- a/libraries/base/Data/Type/Equality.hs
+++ b/libraries/base/Data/Type/Equality.hs
@@ -127,6 +127,61 @@ instance TestEquality ((:~:) a) where
 type family (a :: k) == (b :: k) :: Bool
 infix 4 ==
 
+{-
+This comment explains more about why a poly-kinded instance for (==) is
+not provided. To be concrete, here would be the poly-kinded instance:
+
+type family EqPoly (a :: k) (b :: k) where
+ EqPoly a a = True
+ EqPoly a b = False
+type instance (a :: k) == (b :: k) = EqPoly a b
+
+Note that this overlaps with every other instance -- if this were defined,
+it would be the only instance for (==).
+
+Now, consider
+data Nat = Zero | Succ Nat
+
+Suppose I want
+foo :: (Succ n == Succ m) ~ True => ((n == m) :~: True)
+foo = Refl
+
+This would not type-check with the poly-kinded instance. `Succ n == Succ m`
+quickly becomes `EqPoly (Succ n) (Succ m)` but then is stuck. We don't know
+enough about `n` and `m` to reduce further.
+
+On the other hand, consider this:
+
+type family EqNat (a :: Nat) (b :: Nat) where
+ EqNat Zero     Zero     = True
+ EqNat (Succ n) (Succ m) = EqNat n m
+ EqNat n        m        = False
+type instance (a :: Nat) == (b :: Nat) = EqNat a b
+
+With this instance, `foo` type-checks fine. `Succ n == Succ m` becomes `EqNat
+(Succ n) (Succ m)` which becomes `EqNat n m`. Thus, we can conclude `(n == m)
+~ True` as desired.
+
+So, the Nat-specific instance allows strictly more reductions, and is thus
+preferable to the poly-kinded instance. But, if we introduce the poly-kinded
+instance, we are barred from writing the Nat-specific instance, due to
+overlap.
+
+Even better than the current instance for * would be one that does this sort
+of recursion for all datatypes, something like this:
+
+type family EqStar (a :: *) (b :: *) where
+ EqStar Bool Bool = True
+ EqStar (a,b) (c,d) = a == c && b == d
+ EqStar (Maybe a) (Maybe b) = a == b
+ ...
+ EqStar a b = False
+
+The problem is the (...) is extensible -- we would want to add new cases for
+all datatypes in scope. This is not currently possible for closed type
+families.
+-}
+
 -- all of the following closed type families are local to this module
 type family EqStar (a :: *) (b :: *) where
   EqStar a a = True
diff --git a/libraries/base/Data/Typeable/Internal.hs b/libraries/base/Data/Typeable/Internal.hs
index fa18bf9c60..93b64ef9e9 100644
--- a/libraries/base/Data/Typeable/Internal.hs
+++ b/libraries/base/Data/Typeable/Internal.hs
@@ -1,4 +1,5 @@
 {-# LANGUAGE Unsafe             #-}
+{-# LANGUAGE BangPatterns #-}
 
 -----------------------------------------------------------------------------
 -- |
@@ -22,6 +23,8 @@
            , PolyKinds
            , ConstraintKinds
            , DeriveDataTypeable
+           , DataKinds
+           , UndecidableInstances
            , StandaloneDeriving #-}
 
 module Data.Typeable.Internal (
@@ -50,6 +53,7 @@ module Data.Typeable.Internal (
 import GHC.Base
 import GHC.Word
 import GHC.Show
+import GHC.Read ( Read )
 import Data.Maybe
 import Data.Proxy
 import GHC.Num
@@ -57,13 +61,21 @@ import GHC.Real
 -- import GHC.IORef
 -- import GHC.IOArray
 -- import GHC.MVar
-import GHC.ST           ( ST )
+import GHC.ST           ( ST, STret )
 import GHC.STRef        ( STRef )
 import GHC.Ptr          ( Ptr, FunPtr )
 -- import GHC.Stable
-import GHC.Arr          ( Array, STArray )
+import GHC.Arr          ( Array, STArray, Ix )
+import GHC.TypeLits ( Nat, Symbol, KnownNat, KnownSymbol, natVal', symbolVal' )
 import Data.Type.Coercion
 import Data.Type.Equality
+import Text.ParserCombinators.ReadP ( ReadP )
+import Text.Read.Lex ( Lexeme, Number )
+import Text.ParserCombinators.ReadPrec ( ReadPrec )
+import GHC.Float ( FFFormat, RealFloat, Floating )
+import Data.Bits ( Bits, FiniteBits )
+import GHC.Enum ( Bounded, Enum )
+import Control.Monad ( MonadPlus )
 -- import Data.Int
 
 import GHC.Fingerprint.Type
@@ -251,8 +263,20 @@ type Typeable7 (a :: * -> * -> * -> * -> * -> * -> * -> *) = Typeable a
 {-# DEPRECATED Typeable7 "renamed to 'Typeable'" #-} -- deprecated in 7.8
 
 -- | Kind-polymorphic Typeable instance for type application
-instance (Typeable s, Typeable a) => Typeable (s a) where
-  typeRep# _ = typeRep# (proxy# :: Proxy# s) `mkAppTy` typeRep# (proxy# :: Proxy# a)
+instance {-# INCOHERENT #-} (Typeable s, Typeable a) => Typeable (s a) where
+  typeRep# = \_ -> rep                  -- Note [Memoising typeOf]
+    where !ty1 = typeRep# (proxy# :: Proxy# s)
+          !ty2 = typeRep# (proxy# :: Proxy# a)
+          !rep = ty1 `mkAppTy` ty2
+
+{- Note [Memoising typeOf]
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+See #3245, #9203
+
+IMPORTANT: we don't want to recalculate the TypeRep once per call with
+the proxy argument.  This is what went wrong in #3245 and #9203. So we
+help GHC by manually keeping the 'rep' *outside* the lambda.
+-}
 
 ----------------- Showing TypeReps --------------------
 
@@ -316,6 +340,7 @@ deriving instance Typeable IO
 deriving instance Typeable Array
 
 deriving instance Typeable ST
+deriving instance Typeable STret
 deriving instance Typeable STRef
 deriving instance Typeable STArray
 
@@ -351,8 +376,106 @@ deriving instance Typeable Word64
 
 deriving instance Typeable TyCon
 deriving instance Typeable TypeRep
+deriving instance Typeable Fingerprint
 
 deriving instance Typeable RealWorld
 deriving instance Typeable Proxy
+deriving instance Typeable KProxy
 deriving instance Typeable (:~:)
 deriving instance Typeable Coercion
+
+deriving instance Typeable ReadP
+deriving instance Typeable Lexeme
+deriving instance Typeable Number
+deriving instance Typeable ReadPrec
+
+deriving instance Typeable FFFormat
+
+-------------------------------------------------------
+--
+-- Generate Typeable instances for standard classes
+--
+-------------------------------------------------------
+
+deriving instance Typeable (~)
+deriving instance Typeable Coercible
+deriving instance Typeable TestEquality
+deriving instance Typeable TestCoercion
+
+deriving instance Typeable Eq
+deriving instance Typeable Ord
+
+deriving instance Typeable Bits
+deriving instance Typeable FiniteBits
+deriving instance Typeable Num
+deriving instance Typeable Real
+deriving instance Typeable Integral
+deriving instance Typeable Fractional
+deriving instance Typeable RealFrac
+deriving instance Typeable Floating
+deriving instance Typeable RealFloat
+
+deriving instance Typeable Bounded
+deriving instance Typeable Enum
+deriving instance Typeable Ix
+
+deriving instance Typeable Show
+deriving instance Typeable Read
+
+deriving instance Typeable Functor
+deriving instance Typeable Monad
+deriving instance Typeable MonadPlus
+
+deriving instance Typeable Typeable
+
+
+
+--------------------------------------------------------------------------------
+-- Instances for type literals
+
+{- Note [Potential Collisions in `Nat` and `Symbol` instances]
+
+Kinds resulting from lifted types have finitely many type-constructors.
+This is not the case for `Nat` and `Symbol`, which both contain *infinitely*
+many type constructors (e.g., `Nat` has 0, 1, 2, 3, etc.).  One might think
+that this would increase the chance of hash-collisions in the type but this
+is not the case because the fingerprint stored in a `TypeRep` identifies
+the whole *type* and not just the type constructor.  This is why the chance
+of collisions for `Nat` and `Symbol` is not any worse than it is for other
+lifted types with infinitely many inhabitants.  Indeed, `Nat` is
+isomorphic to (lifted) `[()]`  and `Symbol` is isomorphic to `[Char]`.
+-}
+
+instance KnownNat n => Typeable (n :: Nat) where
+  -- See #9203 for an explanation of why this is written as `\_ -> rep`.
+  typeRep# = \_ -> rep
+    where
+    rep = mkTyConApp tc []
+    tc = TyCon
+           { tyConHash     = fingerprintString (mk pack modu nm)
+           , tyConPackage  = pack
+           , tyConModule   = modu
+           , tyConName     = nm
+           }
+    pack = "base"
+    modu = "GHC.TypeLits"
+    nm   = show (natVal' (proxy# :: Proxy# n))
+    mk a b c = a ++ " " ++ b ++ " " ++ c
+
+
+instance KnownSymbol s => Typeable (s :: Symbol) where
+  -- See #9203 for an explanation of why this is written as `\_ -> rep`.
+  typeRep# = \_ -> rep
+    where
+    rep = mkTyConApp tc []
+    tc = TyCon
+           { tyConHash     = fingerprintString (mk pack modu nm)
+           , tyConPackage  = pack
+           , tyConModule   = modu
+           , tyConName     = nm
+           }
+    pack = "base"
+    modu = "GHC.TypeLits"
+    nm   = show (symbolVal' (proxy# :: Proxy# s))
+    mk a b c = a ++ " " ++ b ++ " " ++ c
+
diff --git a/libraries/base/Data/Unique.hs b/libraries/base/Data/Unique.hs
index 2d30cc18e9..a5c0d6c753 100644
--- a/libraries/base/Data/Unique.hs
+++ b/libraries/base/Data/Unique.hs
@@ -1,5 +1,5 @@
 {-# LANGUAGE Trustworthy #-}
-{-# LANGUAGE MagicHash, DeriveDataTypeable #-}
+{-# LANGUAGE MagicHash, AutoDeriveTypeable #-}
 
 -----------------------------------------------------------------------------
 -- |
diff --git a/libraries/base/Data/Version.hs b/libraries/base/Data/Version.hs
index 23d217634e..8b88486571 100644
--- a/libraries/base/Data/Version.hs
+++ b/libraries/base/Data/Version.hs
@@ -1,5 +1,5 @@
 {-# LANGUAGE Trustworthy #-}
-{-# LANGUAGE DeriveDataTypeable #-}
+{-# LANGUAGE AutoDeriveTypeable #-}
 
 -----------------------------------------------------------------------------
 -- |