[Haskell] really undecidable instances?

[Benjamin Franksen]

On Monday 17 October 2005 15:57, Simon Peyton-Jones wrote:
> | Wolfgang Jeltsch:
> | what ist the problem with instance declarations like the following:
> |
> | 	instance C Int a => D Char [a]
> |
> | Why are such declarations only allowed with
> | -fallow-undecidable-instances in
> | GHC?  How can they result in undecidability?
>
> This one can't.  But it's hard to formulate a general rule.
> -fallow-undecidable-instances simply says that you, the programmer,
> take responsibility for termination.  Without the flag, GHC uses a
> simple but sometimes over-conservative rule

Hi,

I've now been bitten by the same 'over-conservatism' of H98. In my case 
it's

    Non-type variables in constraint: Pretty (tree a)
    (Use -fallow-undecidable-instances to permit this)
    In the context: (Pretty a, Pretty (tree a))

This is the data type declaration:

> data Node23 tree a
>   = N2 (tree a) a (tree a)
>   | N3 (tree a) a (tree a) a (tree a)

and this is the instance, where the error is reported:

> instance (Pretty a, Pretty (tree a)) => Pretty (Node23 tree a) where
>   ...

The class Pretty is from Daan Leijen's pprint library.

I think that the 'non-type variable' refered to above is the application 
(tree a) in the constraint (Pretty (tree a)), which is arguably 
"almost" a type variable. In this case I think it is even more obvious 
that it can't cause a loop, since the LHS clearly has a type 
constructor removed, right?

I mention this mainly because my module is otherwise completely H98 and 
I thought it would be nice to keep it that way. I need the Pretty 
instance for debugging only, so it's not really a show-stopper. Still I 
wonder if somebody knows a work-around that doesn't need a language 
extension (some newtype trick, maybe?).

Ben