[GHC] #13092: family instance consistency checks are too pessimistic

[GHC]

#13092: family instance consistency checks are too pessimistic
-------------------------------------+-------------------------------------
        Reporter:  rwbarton          |                Owner:  rwbarton
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.2.1
       Component:  Compiler          |              Version:  8.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  Phab:D2992
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 I think the Phab is fine, but here's a possible thought for improvement to
 `checkFamInstConsistency`.  Currently it does an all-pairs enumeration,
 and filters out pairs that are already known consistent.  That sounds like
 enumerating a large set and then filtering it.

 What about this.  Take just two imported modules A and B, with
 `dep_finsts` dA and dB resp.  So we know that `A + dA` is consistent and
 `B + dB` is consistent.

 What extra parirwise checks do we need to make to ensure that `uAB` is
 consistent, where
 {{{
   uAB = A + dA + B + dB
 }}}
 (I'm using `+` for set union.)  Well, define
 {{{
    iAB = (A + dA) `intersect` (B + dB)
 }}}
 so that `iAB` is the intersection; certainly it is consistent all of
 `uAB`.  Now define
 {{{
   xA = (A + dA) - iAB
   xB = (B + dB) - iAB
 }}}
 If we check all the pairs with one from `xA` and one from `xB` we are
 done.  So check those and form the union `uAB`.  Now continue by adding in
 one more module, and keep doing that a time.

 The bigger the intersection the better.

 I'm not certain that is better, but it smells better.

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