Weird bug with FDs

Niklas Broberg niklas.broberg at
Thu Jul 6 15:11:01 EDT 2006

I encounter a strange behavior with functional dependencies. Assume we
have a class defined as

class Foo x y | x -> y where
 foo :: x -> y

and another class

class Bar x y where
 bar :: x -> y -> Int

and I want to write the instance declaration

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

Compiling (with 6.4.2, -fallow-undecidable-instances and
-fglasgow-exts) I get the following error message:
    Context reduction stack overflow; size = 21
    Use -fcontext-stack20 to increase stack size to (e.g.) 20
        `$dBar :: Bar y z' arising from use of `bar' at Foo.hs:13:11-13
        [... same thing 20 times ...]
        `$dBar :: Bar y z' arising from use of `bar' at Foo.hs:13:11-13
        `bar :: {bar at [y z]}' arising from use of `bar' at Foo.hs:13:11-13
    When trying to generalise the type inferred for `bar'
      Signature type:     forall x y z. (Foo x y, Bar y z) => x -> z -> Int
      Type to generalise: x -> z -> Int
    In the instance declaration for `Bar x z'

The 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 b) add an explicit type signature
(foo x :: y) in the definition of Bar. The first seems weird since how
could a different, unrelated instance affect the typeability of the
second instance? The second, b), is weird since by the FD x -> y we
should already know that foo x :: y.

GHC 6.4.1 shows the same behavior. Hugs (with -98 +O) accepts the code.

I've submitted a trac ticket, but it would be interesting to hear if
anyone has an explanation to this? :-)



More information about the Glasgow-haskell-users mailing list