On Tue, Aug 24, 2010 at 4:42 PM, Michael Vanier
Adding OverlappingInstances to the language pragmas fixes the problem. My question is: why is this an overlapping instance? It would make sense if Int was an instance of Nat, but it isn't. Is this just a limitation in the way overlapping instances are identified?
The problem is that instance selection doesn't work the (obvious, seemingly-sensible) way you thought it did. In short, instance contexts are only examined after the fact; your second instance describes an instance of Show for *all* n, which of course overlaps absolutely everything. Only after selecting a uniquely matching instance (or, with OverlappingInstances, the "best" match in some sense) are instance contexts taken into consideration, potentially causing a compilation error if the context isn't satisfied, but not discarding the instance and looking for another one instead. The reason it works this way has to do with the nature of type classes being "open". By analogy, imagine a hypothetical extension that allows a function to be defined across multiple modules, with new equations for the function added anywhere, no defined ordering of equations, and equations for such a function automatically brought into scope by importing a module defining one (even if nothing else in the module is), with the particular expression to evaluate being chosen at runtime by pattern matching with all the equations that are in scope. Now add another extension that allows a single argument to match the patterns for multiple equations for a function, with the compiler magically deciding whether, say, ([Just 5, Nothing], _) is a "better" match than ((x:_), []). That's OverlappingInstances, and if it doesn't make your skin crawl a little bit it probably should! There are assorted tricks and hacks with overlapping instances to accomplish various feats of type metaprogramming (usually also involving undecidable instances, which are arguably less unnerving than overlapping), for which the best textbook is probably Oleg's website. It's unfortunately the case that a lot of useful things would require data kinds and/or closed type classes; lacking those, overlapping instances let you fake most of it with only minor loss of sanity points. Fortunately, you don't need to worry about any of that for your particular problem here. - C.