compiler/types/TypeRep.lhs

   1 %
   2 % (c) The University of Glasgow 2006
   3 % (c) The GRASP/AQUA Project, Glasgow University, 1998
   4 %
   5 \section[TypeRep]{Type - friends' interface}
   6
   7 \begin{code}
   8 -- We expose the relevant stuff from this module via the Type module
   9 {-# OPTIONS_HADDOCK hide #-}
  10 {-# LANGUAGE DeriveDataTypeable, DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
  11 module TypeRep (
  12         TyThing(..),
  13         Type(..),
  14         Pred(..),                       -- to friends
  15
  16         Kind, SuperKind,
  17         PredType, ThetaType,      -- Synonyms
  18
  19         -- Functions over types
  20         mkTyConApp, mkTyConTy, mkTyVarTy, mkTyVarTys,
  21         isLiftedTypeKind, isCoercionKind,
  22
  23         -- Pretty-printing
  24         pprType, pprParendType, pprTypeApp,
  25         pprTyThing, pprTyThingCategory,
  26         pprPredTy, pprEqPred, pprTheta, pprForAll, pprThetaArrowTy, pprClassPred,
  27         pprKind, pprParendKind,
  28         Prec(..), maybeParen, pprTcApp, pprTypeNameApp,
  29         pprPrefixApp, pprPred, pprArrowChain, pprThetaArrow,
  30
  31         -- Free variables
  32         tyVarsOfType, tyVarsOfTypes,
  33         tyVarsOfPred, tyVarsOfTheta,
  34         varsOfPred, varsOfTheta,
  35         predSize,
  36
  37         -- Substitutions
  38         TvSubst(..), TvSubstEnv
  39     ) where
  40
  41 #include "HsVersions.h"
  42
  43 import {-# SOURCE #-} DataCon( DataCon, dataConName )
  44
  45 -- friends:
  46 import Var
  47 import VarEnv
  48 import VarSet
  49 import Name
  50 import BasicTypes
  51 import TyCon
  52 import Class
  53
  54 -- others
  55 import PrelNames
  56 import Outputable
  57 import FastString
  58 import Pair
  59
  60 -- libraries
  61 import qualified Data.Data        as Data hiding ( TyCon )
  62 import qualified Data.Foldable    as Data
  63 import qualified Data.Traversable as Data
  64 \end{code}
  65
  66         ----------------------
  67         A note about newtypes
  68         ----------------------
  69
  70 Consider
  71         newtype N = MkN Int
  72
  73 Then we want N to be represented as an Int, and that's what we arrange.
  74 The front end of the compiler [TcType.lhs] treats N as opaque,
  75 the back end treats it as transparent [Type.lhs].
  76
  77 There's a bit of a problem with recursive newtypes
  78         newtype P = MkP P
  79         newtype Q = MkQ (Q->Q)
  80
  81 Here the 'implicit expansion' we get from treating P and Q as transparent
  82 would give rise to infinite types, which in turn makes eqType diverge.
  83 Similarly splitForAllTys and splitFunTys can get into a loop.
  84
  85 Solution:
  86
  87 * Newtypes are always represented using TyConApp.
  88
  89 * For non-recursive newtypes, P, treat P just like a type synonym after
  90   type-checking is done; i.e. it's opaque during type checking (functions
  91   from TcType) but transparent afterwards (functions from Type).
  92   "Treat P as a type synonym" means "all functions expand NewTcApps
  93   on the fly".
  94
  95   Applications of the data constructor P simply vanish:
  96         P x = x
  97
  98
  99 * For recursive newtypes Q, treat the Q and its representation as
 100   distinct right through the compiler.  Applications of the data consructor
 101   use a coerce:
 102         Q = \(x::Q->Q). coerce Q x
 103   They are rare, so who cares if they are a tiny bit less efficient.
 104
 105 The typechecker (TcTyDecls) identifies enough type construtors as 'recursive'
 106 to cut all loops.  The other members of the loop may be marked 'non-recursive'.
 107
 108
 109 %************************************************************************
 110 %*                                                                      *
 111 \subsection{The data type}
 112 %*                                                                      *
 113 %************************************************************************
 114
 115
 116 \begin{code}
 117 -- | The key representation of types within the compiler
 118 data Type
 119   = TyVarTy TyVar       -- ^ Vanilla type variable (*never* a coercion variable)
 120
 121   | AppTy
 122         Type
 123         Type            -- ^ Type application to something other than a 'TyCon'. Parameters:
 124                         --
 125                         --  1) Function: must /not/ be a 'TyConApp',
 126                         --     must be another 'AppTy', or 'TyVarTy'
 127                         --
 128                         --  2) Argument type
 129
 130   | TyConApp
 131         TyCon
 132         [Type]          -- ^ Application of a 'TyCon', including newtypes /and/ synonyms.
 133                         -- Invariant: saturated appliations of 'FunTyCon' must
 134                         -- use 'FunTy' and saturated synonyms must use their own
 135                         -- constructors. However, /unsaturated/ 'FunTyCon's
 136                         -- do appear as 'TyConApp's.
 137                         -- Parameters:
 138                         --
 139                         -- 1) Type constructor being applied to.
 140                         --
 141                         -- 2) Type arguments. Might not have enough type arguments
 142                         --    here to saturate the constructor.
 143                         --    Even type synonyms are not necessarily saturated;
 144                         --    for example unsaturated type synonyms
 145                         --    can appear as the right hand side of a type synonym.
 146
 147   | FunTy
 148         Type
 149         Type            -- ^ Special case of 'TyConApp': @TyConApp FunTyCon [t1, t2]@
 150                         -- See Note [Equality-constrained types]
 151
 152   | ForAllTy
 153         TyCoVar         -- Type variable
 154         Type            -- ^ A polymorphic type
 155
 156   | PredTy
 157         PredType        -- ^ The type of evidence for a type predictate.
 158                         -- Note that a @PredTy (EqPred _ _)@ can appear only as the kind
 159                         -- of a coercion variable; never as the argument or result of a
 160                         -- 'FunTy' (unlike the 'PredType' constructors 'ClassP' or 'IParam')
 161
 162                         -- See Note [PredTy], and Note [Equality predicates]
 163   deriving (Data.Data, Data.Typeable)
 164
 165 -- | The key type representing kinds in the compiler.
 166 -- Invariant: a kind is always in one of these forms:
 167 --
 168 -- > FunTy k1 k2
 169 -- > TyConApp PrimTyCon [...]
 170 -- > TyVar kv   -- (during inference only)
 171 -- > ForAll ... -- (for top-level coercions)
 172 type Kind = Type
 173
 174 -- | "Super kinds", used to help encode 'Kind's as types.
 175 -- Invariant: a super kind is always of this form:
 176 --
 177 -- > TyConApp SuperKindTyCon ...
 178 type SuperKind = Type
 179 \end{code}
 180
 181 Note [Equality-constrained types]
 182 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 183 The type   forall ab. (a ~ [b]) => blah
 184 is encoded like this:
 185
 186    ForAllTy (a:*) $ ForAllTy (b:*) $
 187    FunTy (PredTy (EqPred a [b]) $
 188    blah
 189
 190 -------------------------------------
 191                 Note [PredTy]
 192
 193 \begin{code}
 194 -- | A type of the form @PredTy p@ represents a value whose type is
 195 -- the Haskell predicate @p@, where a predicate is what occurs before
 196 -- the @=>@ in a Haskell type.
 197 -- It can be expanded into its representation, but:
 198 --
 199 -- * The type checker must treat it as opaque
 200 --
 201 -- * The rest of the compiler treats it as transparent
 202 --
 203 -- Consider these examples:
 204 --
 205 -- > f :: (Eq a) => a -> Int
 206 -- > g :: (?x :: Int -> Int) => a -> Int
 207 -- > h :: (r\l) => {r} => {l::Int | r}
 208 --
 209 -- Here the @Eq a@ and @?x :: Int -> Int@ and @r\l@ are all called \"predicates\"
 210 type PredType = Pred Type
 211
 212 data Pred a   -- Typically 'a' is instantiated with Type or Coercion
 213   = ClassP Class [a]            -- ^ Class predicate e.g. @Eq a@
 214   | IParam (IPName Name) a      -- ^ Implicit parameter e.g. @?x :: Int@
 215   | EqPred a a                  -- ^ Equality predicate e.g @ty1 ~ ty2@
 216   deriving (Data.Data, Data.Typeable, Data.Foldable, Data.Traversable, Functor)
 217
 218 -- | A collection of 'PredType's
 219 type ThetaType = [PredType]
 220 \end{code}
 221
 222 (We don't support TREX records yet, but the setup is designed
 223 to expand to allow them.)
 224
 225 A Haskell qualified type, such as that for f,g,h above, is
 226 represented using
 227         * a FunTy for the double arrow
 228         * with a PredTy as the function argument
 229
 230 The predicate really does turn into a real extra argument to the
 231 function.  If the argument has type (PredTy p) then the predicate p is
 232 represented by evidence (a dictionary, for example, of type (predRepTy p).
 233
 234 Note [Equality predicates]
 235 ~~~~~~~~~~~~~~~~~~~~~~~~~~
 236         forall a b. (a ~ S b) => a -> b
 237 could be represented by
 238         ForAllTy a (ForAllTy b (FunTy (PredTy (EqPred a (S b))) ...))
 239 OR
 240         ForAllTy a (ForAllTy b (ForAllTy (c::PredTy (EqPred a (S b))) ...))
 241
 242 The latter is what we do.  (Unlike for class and implicit parameter
 243 constraints, which do use FunTy.)
 244
 245 Reason:
 246         * FunTy is always a *value* function
 247         * ForAllTy is discarded at runtime
 248
 249 We often need to make a "wildcard" (c::PredTy..).  We always use the same
 250 name (wildCoVarName), since it's not mentioned.
 251
 252
 253 %************************************************************************
 254 %*                                                                      *
 255             Simple constructors
 256 %*                                                                      *
 257 %************************************************************************
 258
 259 These functions are here so that they can be used by TysPrim,
 260 which in turn is imported by Type
 261
 262 \begin{code}
 263 mkTyVarTy  :: TyVar   -> Type
 264 mkTyVarTy  = TyVarTy
 265
 266 mkTyVarTys :: [TyVar] -> [Type]
 267 mkTyVarTys = map mkTyVarTy -- a common use of mkTyVarTy
 268
 269 -- | A key function: builds a 'TyConApp' or 'FunTy' as apppropriate to its arguments.
 270 -- Applies its arguments to the constructor from left to right
 271 mkTyConApp :: TyCon -> [Type] -> Type
 272 mkTyConApp tycon tys
 273   | isFunTyCon tycon, [ty1,ty2] <- tys
 274   = FunTy ty1 ty2
 275
 276   | otherwise
 277   = TyConApp tycon tys
 278
 279 -- | Create the plain type constructor type which has been applied to no type arguments at all.
 280 mkTyConTy :: TyCon -> Type
 281 mkTyConTy tycon = mkTyConApp tycon []
 282
 283 isLiftedTypeKind :: Kind -> Bool
 284 -- This function is here because it's used in the pretty printer
 285 isLiftedTypeKind (TyConApp tc []) = tc `hasKey` liftedTypeKindTyConKey
 286 isLiftedTypeKind _                = False
 287
 288 isCoercionKind :: Kind -> Bool
 289 -- All coercions are of form (ty1 ~ ty2)
 290 -- This function is here rather than in Coercion, because it
 291 -- is used in a knot-tied way to enforce invariants in Var
 292 isCoercionKind (PredTy (EqPred {})) = True
 293 isCoercionKind _                    = False
 294 \end{code}
 295
 296
 297 %************************************************************************
 298 %*                                                                      *
 299                         Free variables of types and coercions
 300 %*                                                                      *
 301 %************************************************************************
 302
 303 \begin{code}
 304 tyVarsOfPred :: PredType -> TyCoVarSet
 305 tyVarsOfPred = varsOfPred tyVarsOfType
 306
 307 tyVarsOfTheta :: ThetaType -> TyCoVarSet
 308 tyVarsOfTheta = varsOfTheta tyVarsOfType
 309
 310 tyVarsOfType :: Type -> VarSet
 311 -- ^ NB: for type synonyms tyVarsOfType does /not/ expand the synonym
 312 tyVarsOfType (TyVarTy v)         = unitVarSet v
 313 tyVarsOfType (TyConApp _ tys)    = tyVarsOfTypes tys
 314 tyVarsOfType (PredTy sty)        = varsOfPred tyVarsOfType sty
 315 tyVarsOfType (FunTy arg res)     = tyVarsOfType arg `unionVarSet` tyVarsOfType res
 316 tyVarsOfType (AppTy fun arg)     = tyVarsOfType fun `unionVarSet` tyVarsOfType arg
 317 tyVarsOfType (ForAllTy tyvar ty) = delVarSet (tyVarsOfType ty) tyvar
 318
 319 tyVarsOfTypes :: [Type] -> TyVarSet
 320 tyVarsOfTypes tys = foldr (unionVarSet . tyVarsOfType) emptyVarSet tys
 321
 322 varsOfPred :: (a -> VarSet) -> Pred a -> VarSet
 323 varsOfPred f (IParam _ ty)    = f ty
 324 varsOfPred f (ClassP _ tys)   = foldr (unionVarSet . f) emptyVarSet tys
 325 varsOfPred f (EqPred ty1 ty2) = f ty1 `unionVarSet` f ty2
 326
 327 varsOfTheta :: (a -> VarSet) -> [Pred a] -> VarSet
 328 varsOfTheta f = foldr (unionVarSet . varsOfPred f) emptyVarSet
 329
 330 predSize :: (a -> Int) -> Pred a -> Int
 331 predSize size (IParam _ t)   = 1 + size t
 332 predSize size (ClassP _ ts)  = 1 + sum (map size ts)
 333 predSize size (EqPred t1 t2) = size t1 + size t2
 334 \end{code}
 335
 336 %************************************************************************
 337 %*                                                                      *
 338                         TyThing
 339 %*                                                                      *
 340 %************************************************************************
 341
 342 Despite the fact that DataCon has to be imported via a hi-boot route,
 343 this module seems the right place for TyThing, because it's needed for
 344 funTyCon and all the types in TysPrim.
 345
 346 \begin{code}
 347 -- | A typecheckable-thing, essentially anything that has a name
 348 data TyThing = AnId     Id
 349              | ADataCon DataCon
 350              | ATyCon   TyCon
 351              | ACoAxiom CoAxiom
 352              | AClass   Class
 353
 354 instance Outputable TyThing where
 355   ppr = pprTyThing
 356
 357 pprTyThing :: TyThing -> SDoc
 358 pprTyThing thing = pprTyThingCategory thing <+> quotes (ppr (getName thing))
 359
 360 pprTyThingCategory :: TyThing -> SDoc
 361 pprTyThingCategory (ATyCon _)   = ptext (sLit "Type constructor")
 362 pprTyThingCategory (ACoAxiom _) = ptext (sLit "Coercion axiom")
 363 pprTyThingCategory (AClass _)   = ptext (sLit "Class")
 364 pprTyThingCategory (AnId   _)   = ptext (sLit "Identifier")
 365 pprTyThingCategory (ADataCon _) = ptext (sLit "Data constructor")
 366
 367 instance NamedThing TyThing where       -- Can't put this with the type
 368   getName (AnId id)     = getName id    -- decl, because the DataCon instance
 369   getName (ATyCon tc)   = getName tc    -- isn't visible there
 370   getName (ACoAxiom cc) = getName cc
 371   getName (AClass cl)   = getName cl
 372   getName (ADataCon dc) = dataConName dc
 373 \end{code}
 374
 375
 376 %************************************************************************
 377 %*                                                                      *
 378                         Substitutions
 379       Data type defined here to avoid unnecessary mutual recursion
 380 %*                                                                      *
 381 %************************************************************************
 382
 383 \begin{code}
 384 -- | Type substitution
 385 --
 386 -- #tvsubst_invariant#
 387 -- The following invariants must hold of a 'TvSubst':
 388 --
 389 -- 1. The in-scope set is needed /only/ to
 390 -- guide the generation of fresh uniques
 391 --
 392 -- 2. In particular, the /kind/ of the type variables in
 393 -- the in-scope set is not relevant
 394 --
 395 -- 3. The substition is only applied ONCE! This is because
 396 -- in general such application will not reached a fixed point.
 397 data TvSubst
 398   = TvSubst InScopeSet  -- The in-scope type variables
 399             TvSubstEnv  -- Substitution of types
 400         -- See Note [Apply Once]
 401         -- and Note [Extending the TvSubstEnv]
 402
 403 -- | A substitition of 'Type's for 'TyVar's
 404 type TvSubstEnv = TyVarEnv Type
 405         -- A TvSubstEnv is used both inside a TvSubst (with the apply-once
 406         -- invariant discussed in Note [Apply Once]), and also independently
 407         -- in the middle of matching, and unification (see Types.Unify)
 408         -- So you have to look at the context to know if it's idempotent or
 409         -- apply-once or whatever
 410 \end{code}
 411
 412 Note [Apply Once]
 413 ~~~~~~~~~~~~~~~~~
 414 We use TvSubsts to instantiate things, and we might instantiate
 415         forall a b. ty
 416 \with the types
 417         [a, b], or [b, a].
 418 So the substition might go [a->b, b->a].  A similar situation arises in Core
 419 when we find a beta redex like
 420         (/\ a /\ b -> e) b a
 421 Then we also end up with a substition that permutes type variables. Other
 422 variations happen to; for example [a -> (a, b)].
 423
 424         ***************************************************
 425         *** So a TvSubst must be applied precisely once ***
 426         ***************************************************
 427
 428 A TvSubst is not idempotent, but, unlike the non-idempotent substitution
 429 we use during unifications, it must not be repeatedly applied.
 430
 431 Note [Extending the TvSubst]
 432 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 433 See #tvsubst_invariant# for the invariants that must hold.
 434
 435 This invariant allows a short-cut when the TvSubstEnv is empty:
 436 if the TvSubstEnv is empty --- i.e. (isEmptyTvSubt subst) holds ---
 437 then (substTy subst ty) does nothing.
 438
 439 For example, consider:
 440         (/\a. /\b:(a~Int). ...b..) Int
 441 We substitute Int for 'a'.  The Unique of 'b' does not change, but
 442 nevertheless we add 'b' to the TvSubstEnv, because b's kind does change
 443
 444 This invariant has several crucial consequences:
 445
 446 * In substTyVarBndr, we need extend the TvSubstEnv
 447         - if the unique has changed
 448         - or if the kind has changed
 449
 450 * In substTyVar, we do not need to consult the in-scope set;
 451   the TvSubstEnv is enough
 452
 453 * In substTy, substTheta, we can short-circuit when the TvSubstEnv is empty
 454 \end{code}
 455
 456
 457
 458 %************************************************************************
 459 %*                                                                      *
 460                    Pretty-printing types
 461
 462        Defined very early because of debug printing in assertions
 463 %*                                                                      *
 464 %************************************************************************
 465
 466 @pprType@ is the standard @Type@ printer; the overloaded @ppr@ function is
 467 defined to use this.  @pprParendType@ is the same, except it puts
 468 parens around the type, except for the atomic cases.  @pprParendType@
 469 works just by setting the initial context precedence very high.
 470
 471 \begin{code}
 472 data Prec = TopPrec     -- No parens
 473           | FunPrec     -- Function args; no parens for tycon apps
 474           | TyConPrec   -- Tycon args; no parens for atomic
 475           deriving( Eq, Ord )
 476
 477 maybeParen :: Prec -> Prec -> SDoc -> SDoc
 478 maybeParen ctxt_prec inner_prec pretty
 479   | ctxt_prec < inner_prec = pretty
 480   | otherwise              = parens pretty
 481
 482 ------------------
 483 pprType, pprParendType :: Type -> SDoc
 484 pprType       ty = ppr_type TopPrec ty
 485 pprParendType ty = ppr_type TyConPrec ty
 486
 487 pprKind, pprParendKind :: Kind -> SDoc
 488 pprKind       = pprType
 489 pprParendKind = pprParendType
 490
 491 ------------------
 492 pprPredTy :: PredType -> SDoc
 493 pprPredTy = pprPred ppr_type
 494
 495 pprPred :: (Prec -> a -> SDoc) -> Pred a -> SDoc
 496 pprPred pp (ClassP cls tys) = ppr_class_pred pp cls tys
 497 pprPred pp (IParam ip ty)   = ppr ip <> dcolon <> pp TopPrec ty
 498 pprPred pp (EqPred ty1 ty2) = ppr_eq_pred pp (Pair ty1 ty2)
 499
 500 ------------
 501 pprEqPred :: Pair Type -> SDoc
 502 pprEqPred = ppr_eq_pred ppr_type
 503
 504 ppr_eq_pred :: (Prec -> a -> SDoc) -> Pair a -> SDoc
 505 ppr_eq_pred pp (Pair ty1 ty2) = sep [ pp FunPrec ty1
 506                                     , nest 2 (ptext (sLit "~"))
 507                                     , pp FunPrec ty2]
 508                                -- Precedence looks like (->) so that we get
 509                                --    Maybe a ~ Bool
 510                                --    (a->a) ~ Bool
 511                                -- Note parens on the latter!
 512
 513 ------------
 514 pprClassPred :: Class -> [Type] -> SDoc
 515 pprClassPred = ppr_class_pred ppr_type
 516
 517 ppr_class_pred :: (Prec -> a -> SDoc) -> Class -> [a] -> SDoc
 518 ppr_class_pred pp clas tys = pprTypeNameApp TopPrec pp (getName clas) tys
 519
 520 ------------
 521 pprTheta :: ThetaType -> SDoc
 522 -- pprTheta [pred] = pprPred pred        -- I'm in two minds about this
 523 pprTheta theta  = parens (sep (punctuate comma (map pprPredTy theta)))
 524
 525 pprThetaArrowTy :: ThetaType -> SDoc
 526 pprThetaArrowTy = pprThetaArrow ppr_type
 527
 528 pprThetaArrow :: (Prec -> a -> SDoc) -> [Pred a] -> SDoc
 529 pprThetaArrow _ []      = empty
 530 pprThetaArrow pp [pred]
 531       | noParenPred pred = pprPred pp pred <+> darrow
 532 pprThetaArrow pp preds   = parens (sep (punctuate comma (map (pprPred pp) preds)))
 533                             <+> darrow
 534
 535 noParenPred :: Pred a -> Bool
 536 -- A predicate that can appear without parens before a "=>"
 537 --       C a => a -> a
 538 --       a~b => a -> b
 539 -- But   (?x::Int) => Int -> Int
 540 noParenPred (ClassP {}) = True
 541 noParenPred (EqPred {}) = True
 542 noParenPred (IParam {}) = False
 543
 544 ------------------
 545 instance Outputable Type where
 546     ppr ty = pprType ty
 547
 548 instance Outputable (Pred Type) where
 549     ppr = pprPredTy   -- Not for arbitrary (Pred a), because the
 550                       -- (Outputable a) doesn't give precedence
 551
 552 instance Outputable name => OutputableBndr (IPName name) where
 553     pprBndr _ n = ppr n -- Simple for now
 554
 555 ------------------
 556         -- OK, here's the main printer
 557
 558 ppr_type :: Prec -> Type -> SDoc
 559 ppr_type _ (TyVarTy tv)       = ppr_tvar tv
 560 ppr_type p (PredTy pred)      = maybeParen p TyConPrec $
 561                                 ifPprDebug (ptext (sLit "<pred>")) <> (pprPredTy pred)
 562 ppr_type p (TyConApp tc tys)  = pprTcApp p ppr_type tc tys
 563
 564 ppr_type p (AppTy t1 t2) = maybeParen p TyConPrec $
 565                            pprType t1 <+> ppr_type TyConPrec t2
 566
 567 ppr_type p ty@(ForAllTy {})        = ppr_forall_type p ty
 568 ppr_type p ty@(FunTy (PredTy _) _) = ppr_forall_type p ty
 569
 570 ppr_type p (FunTy ty1 ty2)
 571   = pprArrowChain p (ppr_type FunPrec ty1 : ppr_fun_tail ty2)
 572   where
 573     -- We don't want to lose synonyms, so we mustn't use splitFunTys here.
 574     ppr_fun_tail (FunTy ty1 ty2)
 575       | not (is_pred ty1) = ppr_type FunPrec ty1 : ppr_fun_tail ty2
 576     ppr_fun_tail other_ty = [ppr_type TopPrec other_ty]
 577
 578     is_pred (PredTy {}) = True
 579     is_pred _           = False
 580
 581 ppr_forall_type :: Prec -> Type -> SDoc
 582 ppr_forall_type p ty
 583   = maybeParen p FunPrec $
 584     sep [pprForAll tvs, pprThetaArrowTy ctxt, pprType tau]
 585   where
 586     (tvs,  rho) = split1 [] ty
 587     (ctxt, tau) = split2 [] rho
 588
 589     split1 tvs (ForAllTy tv ty) = split1 (tv:tvs) ty
 590     split1 tvs ty               = (reverse tvs, ty)
 591
 592     split2 ps (PredTy p `FunTy` ty) = split2 (p:ps) ty
 593     split2 ps ty                    = (reverse ps, ty)
 594
 595 ppr_tvar :: TyVar -> SDoc
 596 ppr_tvar tv  -- Note [Infix type variables]
 597   | isSymOcc (getOccName tv)  = parens (ppr tv)
 598   | otherwise                 = ppr tv
 599
 600 -------------------
 601 pprForAll :: [TyVar] -> SDoc
 602 pprForAll []  = empty
 603 pprForAll tvs = ptext (sLit "forall") <+> sep (map pprTvBndr tvs) <> dot
 604
 605 pprTvBndr :: TyVar -> SDoc
 606 pprTvBndr tv
 607   | isLiftedTypeKind kind = ppr_tvar tv
 608   | otherwise             = parens (ppr_tvar tv <+> dcolon <+> pprKind kind)
 609              where
 610                kind = tyVarKind tv
 611 \end{code}
 612
 613 Note [Infix type variables]
 614 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 615 With TypeOperators you can say
 616
 617    f :: (a ~> b) -> b
 618
 619 and the (~>) is considered a type variable.  However, the type
 620 pretty-printer in this module will just see (a ~> b) as
 621
 622    App (App (TyVarTy "~>") (TyVarTy "a")) (TyVarTy "b")
 623
 624 So it'll print the type in prefix form.  To avoid confusion we must
 625 remember to parenthesise the operator, thus
 626
 627    (~>) a b -> b
 628
 629 See Trac #2766.
 630
 631 \begin{code}
 632 pprTcApp :: Prec -> (Prec -> a -> SDoc) -> TyCon -> [a] -> SDoc
 633 pprTcApp _ _ tc []      -- No brackets for SymOcc
 634   = pp_nt_debug <> ppr tc
 635   where
 636    pp_nt_debug | isNewTyCon tc = ifPprDebug (if isRecursiveTyCon tc
 637                                              then ptext (sLit "<recnt>")
 638                                              else ptext (sLit "<nt>"))
 639                | otherwise     = empty
 640
 641 pprTcApp _ pp tc [ty]
 642   | tc `hasKey` listTyConKey = brackets (pp TopPrec ty)
 643   | tc `hasKey` parrTyConKey = ptext (sLit "[:") <> pp TopPrec ty <> ptext (sLit ":]")
 644   | tc `hasKey` liftedTypeKindTyConKey   = ptext (sLit "*")
 645   | tc `hasKey` unliftedTypeKindTyConKey = ptext (sLit "#")
 646   | tc `hasKey` openTypeKindTyConKey     = ptext (sLit "(?)")
 647   | tc `hasKey` ubxTupleKindTyConKey     = ptext (sLit "(#)")
 648   | tc `hasKey` argTypeKindTyConKey      = ptext (sLit "??")
 649
 650 pprTcApp p pp tc tys
 651   | isTupleTyCon tc && tyConArity tc == length tys
 652   = tupleParens (tupleTyConBoxity tc) (sep (punctuate comma (map (pp TopPrec) tys)))
 653   | otherwise
 654   = pprTypeNameApp p pp (getName tc) tys
 655
 656 ----------------
 657 pprTypeApp :: NamedThing a => a -> [Type] -> SDoc
 658 -- The first arg is the tycon, or sometimes class
 659 -- Print infix if the tycon/class looks like an operator
 660 pprTypeApp tc tys = pprTypeNameApp TopPrec ppr_type (getName tc) tys
 661
 662 pprTypeNameApp :: Prec -> (Prec -> a -> SDoc) -> Name -> [a] -> SDoc
 663 -- Used for classes and coercions as well as types; that's why it's separate from pprTcApp
 664 pprTypeNameApp p pp tc tys
 665   | is_sym_occ           -- Print infix if possible
 666   , [ty1,ty2] <- tys  -- We know nothing of precedence though
 667   = maybeParen p FunPrec $
 668     sep [pp FunPrec ty1, pprInfixVar True (ppr tc) <+> pp FunPrec ty2]
 669   | otherwise
 670   = pprPrefixApp p (pprPrefixVar is_sym_occ (ppr tc)) (map (pp TyConPrec) tys)
 671   where
 672     is_sym_occ = isSymOcc (getOccName tc)
 673
 674 ----------------
 675 pprPrefixApp :: Prec -> SDoc -> [SDoc] -> SDoc
 676 pprPrefixApp p pp_fun pp_tys = maybeParen p TyConPrec $
 677                                hang pp_fun 2 (sep pp_tys)
 678
 679 ----------------
 680 pprArrowChain :: Prec -> [SDoc] -> SDoc
 681 -- pprArrowChain p [a,b,c]  generates   a -> b -> c
 682 pprArrowChain _ []         = empty
 683 pprArrowChain p (arg:args) = maybeParen p FunPrec $
 684                              sep [arg, sep (map (arrow <+>) args)]
 685 \end{code}
 686