[I'm widening this to the Haskell list, because overlapping instances are of general interest.] | To determine (SubType y Value) which is just: | (SubType y (Either Double BaseType)) | | it seems to me that GHC should (has to?) use | instance (SubType a b) => SubType a (Either x b) | | I do not see how the other alternative is applicable: | instance SubType a (Either a x) Well, the "target" (Subtype y (Either Double BaseType)) can match against *both* of these instances. It can match instance (SubType a b) => SubType a (Either x b) by taking a=y, x=Double, b=BaseType *If y were instantiated to Double* it could match the second instance declaration too. Now, you say, y is an existential type variable, so it can't be instantiated to Double --- but that's tricky to pin down. Consider: class Show a where show :: a -> String instance Show a => Show [a] where... instance Show [Char] where... f :: Show a => [a] -> String f xs = show xs main = print (f "hello") When doing type inference for 'f' we don't know what 'a' will be instantiated to. Picking the first is arguably wrong if f is called at type String (as it is here). So GHC and Hugs both bleat. Now your situation is an *existential* type variable, not a universal one. But still, if y *was* Double in a particular situation, then the other instance decl "should" apply, perhaps. Or maybe not. GHC simply does not have a satisfactory solution to the overlapping-instance question. Nor, I think, does Hugs. A good start would be for someone to write a "guide to the problems/design-space of overlapping instances". (There is a ton of back email on the Haskell list about this as raw material.) People regularly ask for extensions and/or changes to the way GHC deals with overlap, which I mostly resist, not purely out of laziness -- it's just that I don't want to meddle until we can move to something that is plainly better. I enclose a long comment from GHC's source code that Jeff Lewis wrote on this topic too. Sorry not to be more helpful. It's a bit of a swamp. Simon
| >> test.hs:26: | >> Could not unambiguously deduce (SubType x Value) | >> from the context (SubType x BaseType) | >> The choice of (overlapping) instance declaration | >> depends on the instantiation of `x' | >> Probable fix: | >> Add (SubType x Value) | >> to the existential context of a data constructor | >> Or add an instance declaration for (SubType x Value) | >> arising from use of `inj' at test.hs:26 | >> In the definition of `test': inj x | >> Failed, modules loaded: none. | >> Prelude> | | | -- ----------------------------------------------------------- | -- test.hs | -- ----------------------------------------------------------- | module Test where | | import Control.Monad.Error | | class SubType a b where | inj :: a -> b | prj :: b -> Maybe a | | instance SubType a (Either a x) where | inj = Left | prj = either Just (const Nothing) | | instance (SubType a b) => SubType a (Either x b) where | inj = Right . inj | prj = either (const Nothing) prj | | -- ----------------------------------------------------------- | | type BaseType = Either Integer ( Either Bool () ) | | type Value = (Either Double BaseType) | | data Foo = forall x. (SubType x BaseType) => MkFoo x | | test :: Foo -> Value | test (MkFoo x) = inj x
\subsection{Avoiding a problem with overlapping} Consider this little program: \begin{pseudocode} class C a where c :: a class C a => D a where d :: a instance C Int where c = 17 instance D Int where d = 13 instance C a => C [a] where c = [c] instance ({- C [a], -} D a) => D [a] where d = c instance C [Int] where c = [37] main = print (d :: [Int]) \end{pseudocode} What do you think `main' prints (assuming we have overlapping instances, and all that turned on)? Well, the instance for `D' at type `[a]' is defined to be `c' at the same type, and we've got an instance of `C' at `[Int]', so the answer is `[37]', right? (the generic `C [a]' instance shouldn't apply because the `C [Int]' instance is more specific). Ghc-4.04 gives `[37]', while ghc-4.06 gives `[17]', so 4.06 is wrong. That was easy ;-) Let's just consult hugs for good measure. Wait - if I use old hugs (pre-September99), I get `[17]', and stranger yet, if I use hugs98, it doesn't even compile! What's going on!? What hugs complains about is the `D [a]' instance decl. \begin{pseudocode} ERROR "mj.hs" (line 10): Cannot build superclass instance *** Instance : D [a] *** Context supplied : D a *** Required superclass : C [a] \end{pseudocode} You might wonder what hugs is complaining about. It's saying that you need to add `C [a]' to the context of the `D [a]' instance (as appears in comments). But there's that `C [a]' instance decl one line above that says that I can reduce the need for a `C [a]' instance to the need for a `C a' instance, and in this case, I already have the necessary `C a' instance (since we have `D a' explicitly in the context, and `C' is a superclass of `D'). Unfortunately, the above reasoning indicates a premature commitment to the generic `C [a]' instance. I.e., it prematurely rules out the more specific instance `C [Int]'. This is the mistake that ghc-4.06 makes. The fix is to add the context that hugs suggests (uncomment the `C [a]'), effectively deferring the decision about which instance to use. So, what's the fix? I think hugs has it right. Here's why. Let's try something else out with ghc-4.04. Let's add the following line: d' :: D a => [a] d' = c Everyone raise their hand who thinks that `d :: [Int]' should give a different answer from `d' :: [Int]'. Well, in ghc-4.04, it does. The `optimization' only applies to instance decls, not to regular bindings, giving inconsistent behavior. Old hugs had this same bug. Here's how we fixed it: like GHC, the list of instances for a given class is ordered, so that more specific instances come before more generic ones. For example, the instance list for C might contain: ..., C Int, ..., C a, ... When we go to look for a `C Int' instance we'll get that one first. But what if we go looking for a `C b' (`b' is unconstrained)? We'll pass the `C Int' instance, and keep going. But if `b' is unconstrained, then we don't know yet if the more specific instance will eventually apply. GHC keeps going, and matches on the generic `C a'. The fix is to, at each step, check to see if there's a reverse match, and if so, abort the search. This prevents hugs from prematurely chosing a generic instance when a more specific one exists. --Jeff BUT NOTE [Nov 2001]: we must actually *unify* not reverse-match in this test. Suppose the instance envt had ..., forall a b. C a a b, ..., forall a b c. C a b c, ... (still most specific first) Now suppose we are looking for (C x y Int), where x and y are unconstrained. C x y Int doesn't match the template {a,b} C a a b but neither does C a a b match the template {x,y} C x y Int But still x and y might subsequently be unified so they *do* match. Simple story: unify, don't match.