[GHC] #3108: Do a better job of solving recursive type-class constraints with functional dependencies

[GHC]

#3108: Do a better job of solving recursive type-class constraints with functional
dependencies
--------------------------------------+-------------------------------------
  Reporter:  simonpj                  |          Owner:                  
      Type:  bug                      |         Status:  new             
  Priority:  normal                   |      Milestone:  6.12 branch     
 Component:  Compiler (Type checker)  |        Version:  6.10.1          
  Severity:  normal                   |       Keywords:                  
Difficulty:  Unknown                  |       Testcase:                  
        Os:  Unknown/Multiple         |   Architecture:  Unknown/Multiple
--------------------------------------+-------------------------------------
 This ticket is just to track this interesting thread on the Haskell list,
 concerning recursive type-class constraints:
 http://www.haskell.org/pipermail/haskell/2009-March/021115.html.
 We might want to get back to this when the new constraint solver is in
 place.

 The question concerns the interaction of solving recursive type-class
 constraints, where it is important to aggressively apply functional
 dependencies. Here's Tom Schrijvers's analysis of Ralf's example:

 "The cyclic dictionaries approach is a bit fragile. The problem appears to
 be here that GHC alternates exhaustive phases of constraint reduction and
 functional dependency improvement. The problem is that in your example you
 need both for detecting a cycle.

 This can happen:
 {{{
         C1 Int
         ==> 3rd C1 inst
         C2 Int y, C1 (y,Bool)
         ==> 1st C1 inst
         C2 Int y, C1 y, C1 Bool
         ==> 2nd C1 inst
         C2 Int y, C1 y
         ==> 3rd C1 inst
         C2 Int y, C2 y z, C1 (z,Bool)
         ==>
         ...
 }}}
 where all the constraint are different because fresh variables are
 introduced.

 What you want to happen is:
 {{{
         C1 Int
         ==> 3rd C1 inst
         C2 Int y, C1 (y,Bool)
         ==> 1st C1 inst
         C2 Int y, C1 y, C1 Bool
         ==> 2nd C1 inst
         C2 Int y, C1 y
         ==> C2 FD improvement {Int/y}  <<<<
         C2 Int Int, C1 Int
         ==> C1 Int cycle detected
         C2 Int Int
         ==> C2 1st instance
         {}
 }}}
 It seems that you want improvement to happen at a higher priority than GHC
 does now."

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