[Haskell-cafe] Proposal to solve Haskell's MPTC dilemma

Max Bolingbroke batterseapower at hotmail.com
Fri May 21 03:56:51 EDT 2010


On 21 May 2010 01:58, Carlos Camarao <carlos.camarao at gmail.com> wrote:
> But this type-correct program would become not typeable if
> instances such as the ones referred to before (by Daniel Fischer)

I was thinking this through, and the situation is more complex than I
had thought.

It seems that single param type classes enjoy a nice property:
* Adding an instance to the module defining the class cannot conflict
with any non-orphan instance defined elsewhere
* Adding an instance for a type for a class *to the module defining
that type* cannot conflict with any non-orphan instance defined
elsewhere

As long as you complicate the definition of "orphan", this seems to
still hold for multi-param ones. The change you need is that an
instance defined in a module other than that defining the class must
be non-orphan *in each individual type variable*. So if a module
defined the D and E data types you could make a C D E instance, but a
C D Bool or C Bool E one is considered "orphan" by this definition.

Functional dependencies refine this slightly: if a variable ("a")
functionally determines another ("b"), an instance can be declared
non-orphan as long as the "a" variable is being instantiated with a
data type which is defined in the same module. So if "C a b" has FD "a
|-> b" you can declare an instance for "C D Bool" but not "C Bool D".

With this definition of "orphan" I don't think it is possible to get
the library fragility issue as long as you stick to "non-orphan"
instances by that definition. I haven't tried to prove this, though.

Where this gets more interesting is that GHC's -fwarn-orphans check
does *not* flag a "C D Bool" instance in a module defining D but not C
as an orphan, whether C has a functional dependency or not. It will
only flag an instance as orphan if *all* of the class type variables
are being instantiated to a datatype defined in another module. This
seems like a bug?

So in summary I think I agree with you that your proposed mechanism
does have fragility characteristics similar to FDs as they stand. One
benefit (that I can see) to using explicitly declared FDs is that the
compiler could potentially use those FDs to implement a correct orphan
instance check, such that code that passed the check was guaranteed
not to cause the library fragility issue in those modules that import
it. However, it appears that GHC doesn't currently do this, which is
upsetting.

(Incidentally, the link to your paper is broken, so I haven't actually
been able to read it, sorry!)

Cheers,
Max


More information about the Haskell-Cafe mailing list