[Haskell-cafe] Overlapping Instances with Functional Dependencies

Daniel Brown danb at cs.utexas.edu
Thu Jul 7 12:46:14 EDT 2005

I have the following three programs:

   class Foo a b
   instance Foo (a -> b) (a -> [b])
   instance Foo a a

   class Bar a b | a -> b
   instance Bar (a -> b) (a -> b)
   instance Bar a a

   class Baz a b | a -> b
   instance Baz (a -> b) (a -> [b])
   instance Baz a a

When compiled in ghc 6.4 (with -fglasgow-exts
-fallow-overlapping-instances -fallow-undecidable-instances) Foo
and Bar compile fine, but Baz fails with this error:

       Functional dependencies conflict between instance declarations:
         Baz.hs:2:0: instance Baz (a -> b) (a -> [b])
         Baz.hs:3:0: instance Baz a a

This is how I interpret the error: The fundep says "a uniquely 
determines b", but if you have `Baz (Int -> Int) b`, b is `Int -> [Int]` 
according to the first instance and `Int -> Int` according to the second 
instance. b isn't uniquely determined by a, so the functional dependency 
isn't functional -- thus the conflict.

When confronted with overlapping instances, the compiler chooses the 
most specific one (if it is unique), e.g. `Baz (a -> b) (a -> [b])` is 
more specific than `Baz a a`.

But it seems that the combination of the two features is broken: if the 
most specific instance is chosen before checking the functional 
dependency, then the fundep is satisfied; if the fundep is checked 
before choosing the most specific instance, then it isn't.

Is this a bug, or am I confused?


More information about the Haskell-Cafe mailing list