[bitc-dev] RE: Type Classes and Specialization

[Mark P Jones]

I thought I'd use a separate message to make an additional comment
on your example:

| Suppose I have a type class TC that is parameterized over lists. This
| type class defines a method
| 
|   f : (fn (TC) unit)
| 
| 
| Now suppose that:
|   Interface A defines an instantiation over (list 'a)
|   Interface B defines an instantiation over (list char)
| 
| Now I compile some unit of compilation that has imported *only*
| interface A, but which contains the expression
| 
|   (f (cons #\c nil))  ; that is, a character list
| 
| In this compilation unit, only the instantiation for (list 'a) is in
| scope, so the more precise specialization cannot be used.

Some implementations of Haskell support "overlapping" instances, which
means that the compiler allows instances to overlap with one another,
so long as one of them is strictly more specific than the other.  Thus

  instance TC [a] where ...
  instance TC [Char] where ...

would be allowed together because the latter is more specific than the
former (Note: this is an extension of Haskell, not part of the standard).
However, the following two examples would not be permitted:

  instance TC (a, Bool) where ...
  instance TC (Char, b) where ...

Neither one of these is more specific than the other (either one could
be used to provide an instance for TC (Char, Bool)), so you'll get an
error instead.

Overlapping instances have remained as an occasionally useful, but also
controversial feature since they were first introduced (which is probably
why they are still not part of the official standard).  Your example can
be used to illustrate the kinds of "odd behavior" that they can cause:

  module M where
  class TC a where f :: a -> Bool

  module P where
  import M
  instance TC [a] where f x = False
  pBool = f "hello"

  module Q where
  import M
  import P
  instance TC [Char] where f x = True
  qBool = f "hello"

This example is legal if you run it in a Haskell compiler with support
for overlapping instances ... but you might notice that pBool and qBool
evaluate to different results, even though they have exactly the same
definition.  Of course, it's not uncommon for a single expression to have
different meanings if it appears in different scopes.  But, in the example
above, there is no shadowing or hiding, so everything that was in scope
when pBool was defined is also in scope when qBool is defined.

Different people react to examples like this in different ways but such
things have, so far, kept the Haskell community from making this feature
a standard part of the language.  (The topic remains on the table however
because there are a number of examples where support for overlapping
instances has proved to be rather useful ...)

All the best,
Mark