[GHC] #9210: "overlapping instances" through FunctionalDependencies

[GHC]

#9210: "overlapping instances" through FunctionalDependencies
--------------------------------------------+------------------------------
        Reporter:  rwbarton                 |            Owner:
            Type:  bug                      |           Status:  new
        Priority:  normal                   |        Milestone:
       Component:  Compiler (Type checker)  |          Version:  7.8.2
      Resolution:                           |         Keywords:
Operating System:  Unknown/Multiple         |     Architecture:
 Type of failure:  None/Unknown             |  Unknown/Multiple
       Test Case:                           |       Difficulty:  Unknown
        Blocking:                           |       Blocked By:
                                            |  Related Tickets:
--------------------------------------------+------------------------------
Changes (by simonpj):

 * cc: dreixel (added)


Comment:

 OK, well I tried the effect of solving problem 1 by making the two
 instance declarations illegal.  The changes in FunDeps are simple:
  * Remove altogether the alternative guarded by `| isJust (tcUnifyTys
 bind_fn rtys1' rtys2')`, mentioned above
  * Change the definition of `fdeqs` thus
 {{{
 -                    fdeqs = zipAndComputeFDEqs (\_ _ -> False) rtys1'
 irs2'
 +                    fdeqs = zipAndComputeFDEqs eqType rtys1' irs2'
 }}}
 This resulted in four test-suite failures
 {{{
 Unexpected failures:
    ghci/scripts              ghci047 [bad stderr] (ghci)
    polykinds                 T9106 [stderr mismatch] (normal)
    typecheck/should_compile  FD4 [exit code non-0] (normal)
    typecheck/should_compile  T7875 [exit code non-0] (normal)
 }}}
 All were for the same reason: instance declarations that were previously
 accepted are now rejected.

 I looked a bit more at `T7875`.  It is described by `Note [Weird fundeps]`
 in `TcInteract`, which reads as follows:
 {{{
 Note [Weird fundeps]
 ~~~~~~~~~~~~~~~~~~~~
 Consider   class Het a b | a -> b where
               het :: m (f c) -> a -> m b

            class GHet (a :: * -> *) (b :: * -> *) | a -> b
            instance            GHet (K a) (K [a])
            instance Het a b => GHet (K a) (K b)

 The two instances don't actually conflict on their fundeps,
 although it's pretty strange.  So they are both accepted. Now
 try   [W] GHet (K Int) (K Bool)
 This triggers fudeps from both instance decls; but it also
 matches a *unique* instance decl, and we should go ahead and
 pick that one right now.  Otherwise, if we don't, it ends up
 unsolved in the inert set and is reported as an error.

 Trac #7875 is a case in point.
 }}}
 This does indeed look weird to me. And it's incredibly fragile.  If the
 wanted constraint doesn't '''yet''' match a unique instance decl (perhaps
 because some other constraint has not yet done a unification) then we
 won't pick the instance, so we will generate both (conflicting) fundeps,
 and we will get an error (from the fundep) even though the constraint is
 ultimately solved.  This seems terrible to me.   So I think I'd argue that
 #7875 should be rejected (hence adding Pedro, its author, in cc).

 `FD4` actually comes from #1797, and involves a combination of functional
 dependencies and overlapping instances.  I'm not sure we've ever fully
 thought through this conbination, but rejecting this would indeed make
 people unhappy.

 I have not looked at #9106 or `ghci047`.

 I feel strongly disinclined to dive once more into the functional
 dependency swamp.  If someone (Iavor?  Pedro?) would like to help that
 would be great.

 Until then, I totally agree that the behaviour of this ticket is bizarre
 and wrong. But without help I don't know how to fix it.

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