Type checking for type synonym families

This patch introduces type checking for type families of which associated
type synonyms are a special case. E.g.

        type family Sum n m

        type instance Sum Zero n = n
        type instance Sum (Succ n) m = Succ (Sum n m)

where

        data Zero       -- empty type
        data Succ n     -- empty type

In addition we support equational constraints of the form:

        ty1 ~ ty2

(where ty1 and ty2 are arbitrary tau types) in any context where
type class constraints are already allowed, e.g.

        data Equals a b where
                Equals :: a ~ b => Equals a b

The above two syntactical extensions are disabled by default. Enable
with the -XTypeFamilies flag.

For further documentation about the patch, see:

        * the master plan
          http://hackage.haskell.org/trac/ghc/wiki/TypeFunctions

        * the user-level documentation
          http://haskell.org/haskellwiki/GHC/Indexed_types

The patch is mostly backwards compatible, except for:

        * Some error messages have been changed slightly.

        * Type checking of GADTs now requires a bit more type declarations:
          not only should the type of a GADT case scrutinee be given, but also
          that of any identifiers used in the branches and the return type.

Please report any unexpected behavior and incomprehensible error message 
for existing code.

Contributors (code and/or ideas):
        Tom Schrijvers
        Manuel Chakravarty
        Simon Peyton-Jones
        Martin Sulzmann 
with special thanks to Roman Leshchinskiy

1 files changed, 27 insertions, 52 deletions

diff --git a/compiler/NOTES b/compiler/NOTES
index 8c62750008..db6756e94e 100644
--- a/compiler/NOTES
+++ b/compiler/NOTES
@@ -1,3 +1,30 @@
+Type functions
+~~~~~~~~~~~~~~
+* A Given inst should be a CoVar, not a coercion
+
+* finaliseEqInst should not need to call zonk
+
+* Why do we need fromGivenEqDict?  How could we construct 	
+	a Dict that had an EqPred?
+	newDictBndr should make an EqInst directly
+
+* tc_co should be accessed only inside Inst
+
+* Inst.mkImplicTy needs a commment about filtering out EqInsts
+  How *do* we deal with wanted equalities?
+
+* Inst.instType behaves inconsistently for EqInsts: it should
+  return an EqPred, like the instType' hack in pprDictsTheta
+
+  Consequences: adjust the uses of instType in TcSimplify
+
+* tcDeref* functions are unused, except in tcGenericNormalizeFamInst, when
+  we can equally well use TcMType.lookupTcTyVar
+
+* Coercion.mkEqPredCoI looks very peculiar.
+
+
+
 
 -------------------------
 *** unexpected failure for jtod_circint(opt)
@@ -46,18 +73,6 @@ Cmm parser notes
   do we need to assign to Node?
 
 
--------------------------
-* Relation between separate type sigs and pattern type sigs
-f :: forall a. a->a
-f :: b->b = e   -- No: monomorphic
-
-f :: forall a. a->a
-f :: forall a. a->a  -- OK
-
-f :: forall a. [a] -> [a]
-f :: forall b. b->b = e  ???
-
-
 -------------------------------
 NB: all floats are let-binds, but some non-rec lets
     may be unlifted (with RHS ok-for-speculation)
@@ -118,46 +133,6 @@ completeLazyBind: 	[given a simplified RHS]
 
 
 
-Right hand sides and arguments
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-In many ways we want to treat 
-	(a) the right hand side of a let(rec), and 
-	(b) a function argument
-in the same way.  But not always!  In particular, we would
-like to leave these arguments exactly as they are, so they
-will match a RULE more easily.
-	
-	f (g x, h x)	
-	g (+ x)
-
-It's harder to make the rule match if we ANF-ise the constructor,
-or eta-expand the PAP:
-
-	f (let { a = g x; b = h x } in (a,b))
-	g (\y. + x y)
-
-On the other hand if we see the let-defns
-
-	p = (g x, h x)
-	q = + x
-
-then we *do* want to ANF-ise and eta-expand, so that p and q
-can be safely inlined.   
-
-Even floating lets out is a bit dubious.  For let RHS's we float lets
-out if that exposes a value, so that the value can be inlined more vigorously.
-For example
-
-	r = let x = e in (x,x)
-
-Here, if we float the let out we'll expose a nice constructor. We did experiments
-that showed this to be a generally good thing.  But it was a bad thing to float
-lets out unconditionally, because that meant they got allocated more often.
-
-For function arguments, there's less reason to expose a constructor (it won't
-get inlined).  Just possibly it might make a rule match, but I'm pretty skeptical.
-So for the moment we don't float lets out of function arguments either.
-
 
 Eta expansion
 ~~~~~~~~~~~~~~