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.

Why are you sorry to crowdsource? That's what stackoverflow is *for*! :) — Tyler, Jul 25 '11 at 01:22
It may be closely related to my codebase, perhaps use of type families (I followed the suggestion I got from another question here, http://stackoverflow.com/questions/6798778/help-with-use-of-functional-dependencies ) — gatoatigrado, Jul 25 '11 at 01:49

score 4 · Accepted Answer · answered Jul 25 '11 at 02:00

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.

that's unfortunate, thanks! hopefully someone will build a satsifiability solver based version in the future. — gatoatigrado, Jul 25 '11 at 02:20
If you think class-based error messages are hard to debug now, just wait until somebody puts a sat-solver behind it... — Daniel Wagner, Jul 26 '11 at 01:20
@Daniel Wagner: Could just go all the way to being a logic language and embed Prolog for instance selection. Then if you try to compile something and the instances don't work out, the compiler will just spit out "No". — C. A. McCann, Jul 26 '11 at 02:15

Help interpreting overlapping instances error message

1 Answers1