more undecidable instances, but why

Simon Peyton-Jones
Tue, 22 Oct 2002 10:42:10 +0100

|   instance MArray IOUArray a IO =3D> MArray IOUArray (S a) IO where

| However, GHC complains:
| /nfs/isd/hdaume/projects/MESumm/Linear2/Linear2.hs:76:
|     Non-type variables in constraint: MArray IOUArray a IO
|     (Use -fallow-undecidable-instances to permit this)

| But I don't see why this is undecidable.  As I understand it,
| instances basically arise when context reduction might not
| terminate.  Here, it always will (AFAICS).

In this case it's not undecideable, but GHC isn't clever enough to spot
that.  The point is that that each of the types on the left of the =3D>
are smaller than the types on the right
	MArray IOUArray a IO
Is smaller than
	MArray IOUArray (S a) IO

But GHC isn't clever enough to spot that.  In general it's the halting
problem.  Doubtless there are useful special cases.