Haskell/GHC: overlapping instances reported while context only allows a single one

Question

Dear Haskell/GHC experts,

I don't really understand why GHC reports overlapping instances while only one is actually valid according the provided contexts. For instance, let's consider the following piece of code:

{-# LANGUAGE FlexibleInstances #-}

class C a where
    foo :: a -> String
    foo x = "OK"

instance C Bool
instance (C a) => C [a]
instance (C a) => C [(Char, a)]

main = print $ foo [('a', True)]

Compiling it gives:

Test.hs:13:16: error:
    * Overlapping instances for C [(Char, Bool)]
        arising from a use of `foo'
      Matching instances:
        instance C a => C [a] -- Defined at Test.hs:9:10
        instance C a => C [(Char, a)] -- Defined at Test.hs:11:10
    * In the second argument of `($)', namely `foo [('a', True)]'
      In the expression: print $ foo [('a', True)]
      In an equation for `main': main = print $ foo [('a', True)]

The point is that ('a', True) has type (Char, Bool) which is not an instance of C. Therefore, instance C a => C [a] is not applicable to the value [('a', True)].

Therefore, why does GHC consider it?

The question is really about understanding the behaviour of GHC, not about how to avoid the issue (e.g. using OverlappingInstances). Is it because contexts are not used when "resolving" a function call? And if so, why?

Thanks in advance!

Answer 1

My understanding (could be very wrong):

First, from the documentation:

When matching, GHC takes no account of the context of the instance declaration (context1 etc). GHC's default behaviour is that exactly one instance must match the constraint it is trying to resolve. It is fine for there to be a potential of overlap (by including both declarations (A) and (B), say); an error is only reported if a particular constraint matches more than one.

The -XOverlappingInstances flag instructs GHC to allow more than one instance to match, provided there is a most specific one.

In your case, the type passed to foo is [(Char,Bool)]. This satisfies the generic [a] and the more specialised [(Char,a)]. In the absence of OverlappingInstances flag, the most specific match scenario does not apply, and an error is reported.

Now if you were to tweak your code slightly like so:

instance C Bool
instance (C a) => C [a]
instance (C a) => C (Char, a)

Then there would be no overlap, because a tuple is not a list.