Overlapping Instance Thoughts

[Ashley Yakeley]

At 2002-05-21 07:25, Simon Peyton-Jones wrote:

>Overlapping instances are a terrific swamp and while they
>are interesting I don't think I'm going to spend a lot of
>time on them in the near future, I'm afraid.  But perhaps
>someone else can..

I would say the overlapping instances issue is one of the more important 
ones in the extended language. I'm sure most Haskell programmers have 
been tripped up by it at least once or twice. It's certainly the thing I 
most frequently bang my head against.

There are in fact some different issues here.

1. There are instances that don't actually overlap, but only because of 
class contexts:

    class C a;
    class D a;
    instance C Bool;
    instance (D a) => C a;

GHC rejects this, because it only looks at the instance heads, not the 
contexts. Ideally GHC would accept this as non-overlapping, but then 
prohibit instances of different classes that caused the two instances to 
overlap, such as this:

    instance D Bool;

2. There's also times when the programmer would like instances that 
really do overlap. Now GHC already has a -fallow-overlapping-instances 
flag to allow overlaps where one is a strict subset of the other: the 
more special case takes priority over the more general. But sometimes 
this isn't enough. For instance, while writing a Scheme interpreter, I 
wanted to do something like this:

    newtype Constant a = MkConstant a;

    -- members omitted
	  	class (Monad m) => MonadGettableReference m r where ...

    instance (Monad m) =>
     MonadGettableReference m Constant where ...

   	instance (MonadGettableReference m r) =>
   	 MonadGettableReference (SchemeCPS r (m p)) r where ...

Unfortunately the two instances overlap, here:

    MonadGettableReference (SchemeCPS Constant (m p)) Constant

In fact it wouldn't actually matter which instance was used in this case, 
and I suspect that's typical of good class design. So perhaps an 
-fallow-incoherent-instances flag that just arbitrarily picked one might 
be helpful. Better would be some mechanism for allowing the programmer to 
specify which instances defer to which. Or else extend 
-fallow-overlapping-instances to allow "disambiguating" instances:

   	class C a b;	
   	instance C a ();
   	instance C () a;
   	instance C () ();

Here, the third instance is precisely the overlap of the other two. But 
apparently this too has problems:

>I don't understand all the implications of this.
>For example, what if we have an instance that
>doesn't match C () () now, but may do 'later'
>when a type variable has been instantiated.

I don't doubt Simon PJ when he says this is a terrific swamp. I think any 
work anyone might wish to do cutting through the swamp that ended up in 
the language would be very valuable.

-- 
Ashley Yakeley, Seattle WA