Class instance specificity order (was Re: Fundeps and type equality)

[Tyson Whitehead]

On Thu, 2013-01-10 at 22:17 +0000, Simon Peyton-Jones wrote:
> Is http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensions.html#instance-overlap 
> insufficiently clear?  If so, let's clarify it.

Thanks for getting back to me Simon.  The document says

"For example, consider these declarations:

instance context1 => C Int a     where ... -- (A)
instance context2 => C a   Bool  where ... -- (B)
instance context3 => C Int [a]   where ... -- (C)
instance context4 => C Int [Int] where ... -- (D)

...

The -XOverlappingInstances flag instructs GHC to allow more than one
instance to match, provided there is a most specific one. For example,
the constraint C Int [Int] matches instances (A), (C) and (D), but the
last is more specific, and hence is chosen. If there is no most-specific
match, the program is rejected."

What it doesn't says is how "most-specific match" is computed.  While it
is pretty clear in the given example (one matches exactly), not all
cases are so clear.  For example, which of

instance context1 => C Int b
instance context2 => C a   [[b]]

does C Int [[Int]] match best against?  If there isn't currently a good
way to resolve this, I would like to suggest the type-shape measure I
proposed in that paper I wrote up awhile back could be used.

Thanks!  -Tyson