Generic solution to (Eq, Show) overlapping instances issue when defining class (* -> *)

Question

Stack has many threads on overlapping instances, and while these are helpful in explaining the source of the problem, I am still not clear as to how to redesign my code for the problem to go away. While I will certain invest more time and effort in going through the details of existing answers, I will post here the general pattern which I have identified as creating the problem, in the hope that a simple and generic answer exists: I typically find myself defining a class such as:

{-# LANGUAGE FlexibleInstances #-}
class M m where
  foo :: m v -> Int
  bar :: m v -> String

together with the instance declarations:

instance (M m) => Eq (m v) where
  (==) x y = (foo x) == (foo y)      -- details unimportant

instance (M m) => Show (m v) where
  show = bar                         -- details unimportant

and in the course of my work I will inevitably create some data type:

data A v = A v

and declare A as an instance of class M:

instance M A where
  foo x = 1                           -- details unimportant
  bar x = "bar"

Then defining some elements of A Integer:

x = A 2
y = A 3

I have no issue printing x and y or evaluating the Boolean x == y, but if I attempt to print the list [x] or evaluate the Boolean [x] == [y], then the overlapping instance error occurs:

main = do
 print x                                     -- fine
 print y                                     -- fine
 print (x == y)                              -- fine
 print [x]                                   -- overlapping instance error
 if [x] == [y] then return () else return () -- overlapping instance error

The cause of these errors is now very clear I think: they stem from the existing instance declarations instance Show a => Show [a] and instance Eq a => Eq [a] and while it is true that [] :: * -> * has not yet been declared as an instance of my class M, there is nothing preventing someone doing so at some point: so the compiler ignores the context of instance declarations.

When faced with the pattern I have described, how can it be re-engineered to avoid the problem?

Answer 1

There's no backtracking in instance search. Instances are matched purely based on the syntactic structure of the instance head. That means instance contexts are not accounted for during instance resolution.

So, when you write

instance (M m) => Show (m v) where
    show = bar

you're saying "Here is an instance for Show, for any type of the form m v". Since [x] :: [] (A Int) is indeed a type of the form m v (set m ~ [] and v ~ A Int), instance search for Show [A Int] turns up two candidates:

instance Show a => Show [a]
instance M m => Show (m v)

Like I said, the type checker doesn't look at the instances' contexts when selecting an instance, so these two instances are overlapping.

The fix is to not declare instances like Show (m v). As a general rule, it's a bad idea to declare instances whose head is composed purely of type variables. Every instance you write should start with an honest-to-goodness type constructor, and you should approach instances which don't fit that pattern with suspicion.

Supplying a newtype for your default instances is a fairly standard design (see, for example, WrappedBifunctor's Functor instance),

newtype WrappedM m a = WrappedM { unwrapM :: m a }

instance M m => Show (WrappedM m a) where
    show = bar . unwrapM

as is giving a default implementation of the function at the top level (see eg foldMapDefault):

showDefault = bar