Fri, 9 Feb 2001 15:49:45 -0500
On Fri, Feb 09, 2001 at 12:05:09PM -0500, Dylan Thurston wrote:
> On Thu, Feb 08, 2001 at 04:06:24AM +0000, Marcin 'Qrczak' Kowalczyk wrote:
> > You can put Num a in some instance's context, but you can't
> > put Convertible Integer a. It's because instance contexts must
> > constrain only type variables, which ensures that context reduction
> > terminates (but is sometimes overly restrictive). There is ghc's
> > flag -fallow-undecidable-instances which relaxes this restriction,
> > at the cost of undecidability.
> Ah! Thanks for reminding me; I've been using Hugs, which allows these
> instances. Is there no way to relax this restriction while
> maintaining undecidability?
After looking up the Jones-Jones-Meijer paper and thinking about it
briefly, it seems to me that the troublesome cases (when "reducing" a
context gives a more complicated context) can only happen with type
constructructors, and not with simple types. Would this work? I.e.,
if every element of an instance context is required to be of the form
C a_1 ... a_n,
with each a_i either a type variable or a simple type, is type
checking decidable? (Probably I'm missing something.)
If this isn't allowed, one could still work around the problem:
class (Convertible Integer a) => ConvertibleFromInteger a
at the cost of sticking in nuisance instance declarations.
Note that this problem arises a lot. E.g., suppose I have
class (Field k, Additive v) => VectorSpace k v ...
and then I want to talk about vector spaces over Float.