Help interpreting overlapping instances error message

Question

I'm stumped on this overlapping instances error message. Sorry this is a nontrivial project, but the error should be local to the type signatures.

First, I declare f to be of a certain type,

let f = undefined :: (CompNode Int)

Then, I try to call my function pshow :: PrettyShow a => a -> String on it. I get this error message.

> pshow f

<interactive>:1:1:
    Overlapping instances for PrettyShow (CompNode Int)
      arising from a use of `pshow'
    Matching instances:
      instance (G.Graph g, PrettyShow (G.Vertex g)) => PrettyShow g
        -- Defined at Graph.hs:61:10-57
      instance (PrettyShow a, Show a) => PrettyShow (CompNode a)
        -- Defined at Interpreter.hs:61:10-58

The problem is that CompNode Int is not a graph, so I don't think the first matching instance should be triggering. (The second one is the one I want to execute.) Indeed, if I write a function that requires its argument to be a graph,

> :{
| let g :: G.Graph a => a -> a
|     g = id
| :}

and then call it on f, I get the expected no instance error message,

> g f

<interactive>:1:1:
    No instance for (G.Graph (CompNode Int))

Thanks in advance, sorry to crowdsource. I'm using GHC 7.0.4.

Answer 1

The problem is that CompNode Int is not a graph, so I don't think the first matching instance should be triggering.

You would think that, but unfortunately it doesn't work that way.

When GHC is selecting an instance, it looks only at the head, i.e., the part after the class name. Only after instance selection is done does it examine the context, i.e., the part before the =>. Mismatches in the context can cause the instance to be rejected and result in a type-checking error, but they won't cause GHC to backtrack and look for another instance.

So, given these instances:

instance (G.Graph g, PrettyShow (G.Vertex g)) => PrettyShow g

instance (PrettyShow a, Show a) => PrettyShow (CompNode a)

...if we ignore the context, they look like this:

instance PrettyShow g

instance PrettyShow (CompNode a)

Which should make it clear that the first instance is completely general and overlaps absolutely everything.

In some cases you can use the OverlappingInstances extension, but that doesn't change the above behavior; rather, it lets GHC resolve ambiguous instances by picking the uniquely most-specific one, if such exists. But using overlapping instances can be tricky and lead to cryptic errors, so I'd encourage you to first rethink the design and see if you can avoid the issue entirely.

That said, in the particular example here, CompNode a is indeed an unambiguously more specific match for CompNode Int, so GHC would select it instead of the general instance.