[GHC] #10318: Cycles in class declaration (via superclasses) sometimes make sense.

[GHC]

#10318: Cycles in class declaration (via superclasses) sometimes make sense.
-------------------------------------+-------------------------------------
        Reporter:  ekmett            |                   Owner:
            Type:  feature request   |                  Status:  new
        Priority:  normal            |               Milestone:
       Component:  Compiler (Type    |                 Version:  7.10.1
  checker)                           |                Keywords:
      Resolution:                    |            Architecture:
Operating System:  Unknown/Multiple  |  Unknown/Multiple
 Type of failure:  GHC rejects       |               Test Case:
  valid program                      |                Blocking:
      Blocked By:                    |  Differential Revisions:
 Related Tickets:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 OK, well I don't understand much of comment:2, but I'll take it on trust.

 What is difficult about recursive superclasses? I'll use the example in
 the Description.

  * '''"Given" superclasses'''.  Suppose we have
 {{{
 f :: C a => ....
 }}}
   and on f's RHS we have the constraint `(D a)`.  GHC treats `(C a)` as a
 "given", and then adds all of `C`'s superclasses as "givens" too, and
 their superclasses, and so on; in case they are useful to prove the
 constraints arising from f's RHS.  For example, `(D a)` might be a distant
 superclass of `(C a)`.

  If there are an infinite number of superclasses, this "add all
 superclasses" idea isn't going to work.

  I expect you'll say "well, in my case `Frac (Frac a) ~ Frac a`, so the
 second-level superclass is the same as the first".  That may be true, but
 it requires somewhat-sophisticated reasoning; a kind of fixpoint
 calculation.  I can see it might be possible, but the penalty for (the
 programmer) getting it wrong is severe; the type checker goes into a loop.

  * '''"Wanted" superclasses'''.Similarly, for "wanted" constraints we
 fluff up the superclases in case one of them has a functional dependency
 that will help us make progress.

  * '''Instance declarations'''.  In an instance declaration we must cough
 up a witness for the superclass.  This part might not be too hard.  At
 lesat in the monomorphic cases you give, like `instance IntegralDomain
 Integer`, we seek an instance for `IntegralDomain (Frac Integer)`, which
 is just `IntegralDomain Rational`, and we have that.  Again things could
 go badly wrong, but I think the existing superclass code might "just
 work".

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