Changes between Initial Version and Version 1 of Ticket #816


Ignore:
Timestamp:
Jul 7, 2006 10:53:17 AM (9 years ago)
Author:
simonpj
Comment:

Great report. This is a nice simple example of something that has only shown up in complicated programs so far.

Here's what happens. In the instance decl

instance (Foo x y, Bar y z) => Bar x z where
 bar x z = bar (foo x) z

Ghc solves the following problem:

   HAS: (Foo x y, Bar y z)
   WANTS: (Foo x y', Bar y' z)

The (Foo x y') arises from the call to foo, and the (Bar y' z) from the call to bar.

Now, if we did improvement now, we'd see that y'=y. But GHC doesn't. For historical reasons, it alternates constraint simplification with improvement. So it sees (Bar y' z). Yes! That matches an instance declaration! So it removes tha constraint and adds (Foo x y, Bar y z). And then it does that repeatedly.

The solution is to do improvement more eagerly, which will form part of my upcoming house-cleaning operation on constraint solving.

Short term: you are stuck. But this bug report makes sure I'll fix it in a while.

Simon

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #816

    • Property Owner set to simonpj
  • Ticket #816 – Description

    initial v1  
    1 I encounter a strange behavior with functional dependencies. Assume we have a class defined as
    2 
     1I encounter a strange behavior with functional dependencies. Consider this program
     2{{{
    33class Foo x y | x -> y where
    44 foo :: x -> y
    5 
    6 and another class
    75
    86class Bar x y where
    97 bar :: x -> y -> Int
    108
    11 and I want to write the instance declaration
    12 
    139instance (Foo x y, Bar y z) => Bar x z where
    1410 bar x z = bar (foo x) z
    15 
     11}}}
    1612Compiling (with 6.4.2, -fallow-undecidable-instances and -fglasgow-exts) I get the following error message:
    17 <error>
     13{{{
    1814Foo.hs:12:0:
    1915    Context reduction stack overflow; size = 21
     
    2723      Type to generalise: x -> z -> Int
    2824    In the instance declaration for `Bar x z'
    29 </error>
     25}}}
    3026
    3127The declaration requires undecidable instances, but I doubt that the problem comes from that. What makes it even more weird is that I can get this to compile, and behave as expected, if I do one of a) declare an instance of Bar for any type, or