[Haskell] Overapping instances [Was: What is the best way to write adapters?]

[oleg at pobox.com]

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....