[GHC] #9334: Implement "instance chains"

[GHC]

#9334: Implement "instance chains"
-------------------------------------+-------------------------------------
              Reporter:  diatchki    |             Owner:  diatchki
                  Type:  feature     |            Status:  new
  request                            |         Milestone:
              Priority:  normal      |           Version:  7.9
             Component:  Compiler    |          Keywords:
  (Type checker)                     |  Operating System:  Unknown/Multiple
            Resolution:              |   Type of failure:  None/Unknown
Differential Revisions:              |         Test Case:
          Architecture:              |          Blocking:
  Unknown/Multiple                   |
            Difficulty:  Unknown     |
            Blocked By:              |
       Related Tickets:              |
-------------------------------------+-------------------------------------

Comment (by goldfire):

 I agree with Iavor -- it would be great to see instance chains for real.

 There are two further observations I'd like to make, though:

 1. Instance chains can, I believe, be simulated accurately with closed
 type families. The encoding is bulky, and I think having real instance
 chains is much better than what we have in 7.8, but an eager programmer
 can use closed type families today. For example, Iavor's example could be
 written

 {{{
 type family ChooseStateMInstance x y where
   ChooseStateMInstance (StateT s m) s = 0
   ChooseStateMInstance (t m) s = 1

 class StateM' (n :: Nat) x y where ...

 instance Monad m => StateM' 0 (StateT s m) s where ...
 instance (MonadTrans t, StateM m s) => StateM' 1 (t m) s where ...

 type StateM s m = StateM' (ChooseStateMInstance s m) s m
 }}}

     Like I said, it's not pretty, but I believe it works.

 2. This doesn't necessarily mean that we'll never need overlapping
 instances -- instance chains seem to only work when the overlap would be
 contained only in one module. Some programs require inter-module overlap
 (say, for a global "default" instance).

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