Ben Yu wrote:
The instance declaration is like this: instance FwdSig Native instance FwdSig Def instance FwdSig d => Sig d instance Sig XXX
Neither Native nor Def are direct instances of Sig. And this XXX, it is an instance of Sig, not a FwdSig.
As you can see, there's no real overlapping at all if we take the "FwdSig d =>" as a precondition for "Sig d".
You have pointed out one of the most confusing issues when dealing with typeclasses. One has the temptation to view
class Foo a instance Foo Int instance (Real a) => Foo a instance Foo a
something like
foo 5 = <body1> foo a | is_real a = <body2> foo a = <body3>
But there is a great difference. The typechecker chooses which instance to use based entirely on the shape of the types described in the instance, disregarding the constraints. In the Foo example, if we drop the constraints, we get
instance Foo Int instance Foo a instance Foo a
It's immediately obvious that there is no way the compiler could choose between the second and the third instance. And so we get a duplicate instances error. If we remove the third instance for example, we still get the problem: if the type in question is Int, which instance, the first or the second, should the compiler choose. The flag -fallow-overlapping-instances increases the compilers's IQ and so the compiler notices that the "Foo Int" is a specialization of "Foo a" (that is, there exists a substitution a->Int which makes "Foo a" identical to "Foo Int"). Therefore, if the instances can be so ordered, the compiler chooses the most specific applicable instance. After the compiler chose the instance, the compiler _becomes committed_ to it. Then the compiler notices constraints (e.g., Real a) and checks if they are satisfied. If they are not -- the typechecking fails. The compiler makes no attempt to choose another instance (more general one, if any) and see if that would work out. This is in the marked contrast with functional clauses (and with Prolog), where the failure of a guard on one clause causes another clause to be tried. If the compiler had taken instance constraints into account when choosing class instances, great many things would be possible. For example, we could easily dispatch on a class of a type of a value. That is, we could write class Foo a where what_is_it:: a -> String instance (Num a) => Foo a where what_is_it _ = "a number" instance (Monad a) => Foo a where what_is_it = "an action" In generally, we could implement `instanceOf' in a robust and succinct way. I guess history plays some part: in Haskell98, which does not permit overlapping instances, there can be no more second chances. If the instance constraints failed, that is it. I do want to point out that adding 'backtracking' to the instance choosing algorithm isn't that trivial. The first question is: should we permit instances that are truly duplicates, like "instance (Real a) => Foo a" and "instance Foo a" above. Many people would say yes. However, we cannot tell which of these instances is more general (syntactically, they are both "Foo a". There is generally no ordering on constraints). So, absent of a substitution-induced ordering, we are forced to resort to textual ordering. If two instances are otherwise the same, the one that appears first should be tried first. However, what does it mean to "textually appear first"? If one instance is declared in one module and the other is in another module (imported via a third module), which of them appears first? We are confronted with the eternal open/closed world issue. To see where it can lead us, one may wish to look at the XSLT Recommendation. http://www.w3.org/TR/1999/REC-xslt-19991116#conflict The XSLT processor likewise has the task of choosing the most appropriate template. The processor has to mind 'modes', import precedence, and even compute priorities of patterns. Curiously, the wildcard '*' gets the priority of -0.5. Integers are not enough for them. I wonder if this stuff is already in HaWiki....