[Haskell-cafe] the overlapping instance that wasn't?

[C. McCann]

On Tue, Aug 24, 2010 at 4:42 PM, Michael Vanier <mvanier42 at gmail.com> wrote:
> 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.