[GHC] #11427: TypeSynonyms not deduced

[GHC]

#11427: TypeSynonyms not deduced
-------------------------------------+-------------------------------------
        Reporter:  phadej            |                Owner:
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1-rc1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 This is very delicate.  And regrettably un-documented.

 It's explained in great detail in `Note [Recursive superclasses]` in
 `TcInstDcls`.  I append the text below.

 In this case GHC is being a little over-conservative, but I don't know how
 to do it better. You can work around it in your example in comment:3 by
 adding `MyEq a` to the offending instance declaration:
 {{{
 instance (MyEq a, MyOrd a) => MyClass a where
   mydef x = myeq x x
 }}}

 Simon

 {{{
 Note [Recursive superclasses]
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 See Trac #3731, #4809, #5751, #5913, #6117, #6161, which all
 describe somewhat more complicated situations, but ones
 encountered in practice.

 See also tests tcrun020, tcrun021, tcrun033, and Trac #11427

 ----- THE PROBLEM --------
 The problem is that it is all too easy to create a class whose
 superclass is bottom when it should not be.

 Consider the following (extreme) situation:
         class C a => D a where ...
         instance D [a] => D [a] where ...   (dfunD)
         instance C [a] => C [a] where ...   (dfunC)
 Although this looks wrong (assume D [a] to prove D [a]), it is only a
 more extreme case of what happens with recursive dictionaries, and it
 can, just about, make sense because the methods do some work before
 recursing.

 To implement the dfunD we must generate code for the superclass C [a],
 which we had better not get by superclass selection from the supplied
 argument:
        dfunD :: forall a. D [a] -> D [a]
        dfunD = \d::D [a] -> MkD (scsel d) ..

 Otherwise if we later encounter a situation where
 we have a [Wanted] dw::D [a] we might solve it thus:
      dw := dfunD dw
 Which is all fine except that now ** the superclass C is bottom **!

 The instance we want is:
        dfunD :: forall a. D [a] -> D [a]
        dfunD = \d::D [a] -> MkD (dfunC (scsel d)) ...

 ----- THE SOLUTION --------
 The basic solution is simple: be very careful about using superclass
 selection to generate a superclass witness in a dictionary function
 definition.  More precisely:

   Superclass Invariant: in every class dictionary,
                         every superclass dictionary field
                         is non-bottom

 To achieve the Superclass Invariant, in a dfun definition we can
 generate a guaranteed-non-bottom superclass witness from:
   (sc1) one of the dictionary arguments itself (all non-bottom)
   (sc2) an immediate superclass of a smaller dictionary
   (sc3) a call of a dfun (always returns a dictionary constructor)

 The tricky case is (sc2).  We proceed by induction on the size of
 the (type of) the dictionary, defined by TcValidity.sizeTypes.
 Let's suppose we are building a dictionary of size 3, and
 suppose the Superclass Invariant holds of smaller dictionaries.
 Then if we have a smaller dictionary, its immediate superclasses
 will be non-bottom by induction.

 What does "we have a smaller dictionary" mean?  It might be
 one of the arguments of the instance, or one of its superclasses.
 Here is an example, taken from CmmExpr:
        class Ord r => UserOfRegs r a where ...
 (i1)   instance UserOfRegs r a => UserOfRegs r (Maybe a) where
 (i2)   instance (Ord r, UserOfRegs r CmmReg) => UserOfRegs r CmmExpr where

 For (i1) we can get the (Ord r) superclass by selection from (UserOfRegs r
 a),
 since it is smaller than the thing we are building (UserOfRegs r (Maybe
 a).

 But for (i2) that isn't the case, so we must add an explicit, and
 perhaps surprising, (Ord r) argument to the instance declaration.

 Here's another example from Trac #6161:

        class       Super a => Duper a  where ...
        class Duper (Fam a) => Foo a    where ...
 (i3)   instance Foo a => Duper (Fam a) where ...
 (i4)   instance              Foo Float where ...

 It would be horribly wrong to define
    dfDuperFam :: Foo a -> Duper (Fam a)  -- from (i3)
    dfDuperFam d = MkDuper (sc_sel1 (sc_sel2 d)) ...

    dfFooFloat :: Foo Float               -- from (i4)
    dfFooFloat = MkFoo (dfDuperFam dfFooFloat) ...

 Now the Super superclass of Duper is definitely bottom!

 This won't happen because when processing (i3) we can use the
 superclasses of (Foo a), which is smaller, namely Duper (Fam a).  But
 that is *not* smaller than the target so we can't take *its*
 superclasses.  As a result the program is rightly rejected, unless you
 add (Super (Fam a)) to the context of (i3).
 }}}

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11427#comment:4>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler