Overlapping multi-parameter instances and instance specificity

Question

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE FlexibleContexts #-}
module OverlappingSpecificsError where

class EqM a b where
    (===) :: a -> b -> Bool

instance {-# OVERLAPPABLE #-} Eq a => EqM a a where
    a === b = a == b

instance {-# OVERLAPPABLE #-} EqM a b where
    a === b = False

aretheyreallyeq :: (Eq a, Eq b) => Either a b -> Either a b -> Bool
aretheyreallyeq (Left a1) (Right b2) = a1 == b2

aretheyeq :: (Eq a, Eq b) => Either a b -> Either a b -> Bool
aretheyeq (Left a1) (Right b2) = a1 === b2

Neither aretheyreallyeq or aretheyeq compile, but the error for aretheyreallyeq makes sense to me, and also tells me that aretheyeq should not give an error: One of the instances that GHCi suggests are possible for EqM in aretheyeq should be impossible due to the same error on aretheyreallyeq. What's going on?

The point is, GHCi insists that both of the instances of EqM are applicable in aretheyeq. But a1 is of type a and b2 is of type b, so in order for the first instance to be applicable, it would have to have the types a and b unify.

But this should not be possible, since they are declared as type variables at the function signature (that is, using the first EqM instance would give rise to the function being of type Either a a -> Either a a -> Bool, and the error in aretheyreallyeq tells me that GHCi will not allow that (which is what I expected anyway).

Am I missing something, or is this a bug in how overlapping instances with multi-parameter type classes are checked?

I am thinking maybe it has to do with the fact that a and b could be further instantiated later on to the point where they are equal, outside aretheyeq, and then the first instance would be valid? But the same is true for aretheyreallyeq. The only difference is that if they do not ever unify we have an option for aretheyeq, but we do not for aretheyreallyeq. In any case, Haskell does not have dynamic dispatch for plenty of good and obvious reasons, so what is the fear in committing to the instance that will always work regardless of whether later on a and b are unifiable? Maybe there is some way to present this that would make choosing the instance when calling the function possible in some way?

It is worth noting that if I remove the second instance, then the function obviously still does not compile, stating that no instance EqM a b can be found. So if I do not have that instance, then none works, but when that one works, suddenly the other does too and I have an overlap? Smells like bug to me miles away.

You might want to compare types a and b for equality at runtime instead of compile time. If so, you could use Typeable a, Typeable b as an additional constraint. Note that, if you do, you will have to satisfy the constraints at each call. — chi

Alexey Romanov Alexey Romanov · Accepted Answer · 2020-02-13T08:09:44

It isn't a bug in sense of working exactly as documented. Starting with

Now suppose that, in some client module, we are searching for an instance of the target constraint (C ty1 .. tyn). The search works like this:

The first stage of finding candidate instances works as you expect; EqM a b is the only candidate and so the prime candidate. But the last step is

Now find all instances, or in-scope given constraints, that unify with the target constraint, but do not match it. Such non-candidate instances might match when the target constraint is further instantiated. If all of them are incoherent top-level instances, the search succeeds, returning the prime candidate. Otherwise the search fails.

The EqM a a instance falls into this category, and isn't incoherent, so the search fails. And you can achieve the behavior you want by marking it as {-# INCOHERENT #-} instead of overlappable.

Overlapping multi-parameter instances and instance specificity

4 Answers