On 21 May 2010 01:58, Carlos Camarao
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