[GHC] #9334: Implement "instance chains"

[GHC]

#9334: Implement "instance chains"
-------------------------------------+-------------------------------------
        Reporter:  diatchki          |                   Owner:  diatchki
            Type:  feature request   |                  Status:  new
        Priority:  normal            |               Milestone:
       Component:  Compiler (Type    |                 Version:  7.9
  checker)                           |  Differential Revisions:
        Keywords:                    |            Architecture:
Operating System:  Unknown/Multiple  |  Unknown/Multiple
 Type of failure:  None/Unknown      |              Difficulty:  Unknown
       Test Case:                    |              Blocked By:
        Blocking:                    |         Related Tickets:
-------------------------------------+-------------------------------------
 It would be useful to implement a version of "instance chains" [1] in GHC,
 which would eliminate the need for OVERLAPPING_INSTANCES in most (all
 practcial?) programs.

 The idea is that programmers can explicitly group and order instances into
 an "instance chain".  For example:
 {{{
 instance (Monad m)                  => StateM (StateT s m) s where ...
 else     (MonadTrans t, StateM m s) => StateM (t m)        s where ...
 }}}

 When GHC searches for instances, the instances in a chain are considered
 together and in order, starting with the first one:

   1. If the goal matches the current instance's head, then this instance
 is selected and the rest are ignored, as if they were not there;

   2. If the goal does not match the current instance's head, AND it does
 not unify with the current instance's head, then we skip the instance and
 proceed to the next member of the chain;

   3. If the goal does not match the current instance's head, but it does
 unify with it, then we cannot use this chain to solve the goal.

 In summary: earlier instances in a chain "hide" later instances, and later
 instances can be reached only if we are sure that none of the previous
 instance will match.


 [1] http://web.cecs.pdx.edu/~mpj/pubs/instancechains.pdf

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