Type class problem

[oleg@pobox.com]

Simon Peyton-Jones wrote:

> > instance (Show (f (Mu f))) => Show (Mu f) where
> >    show (In x) = show x
> >
> > instance Show (N (Mu N)) where
> >    show Z = "Z"
> >    show (S k) = "S "++show k

> But again, it's fragile isn't it? You are dicing with non-termination
> if you have instance declarations where the stuff before the '=>' is more
> complicated than the stuff after the '=>'.  A less carefully written
> instance for Show (N (Mu N)) would make the type checker loop.

That's true that care is required. However, the same care is required
when we want to write 'fix' or a set of mutually recursive type
aliases. We have to introduce a real constructor somewhere to break
the loop. I'm curious if you could post an example of

> You are dicing with non-termination
> if you have instance declarations where the stuff before the '=>' is more
> complicated than the stuff after the '=>'. 

I'm wondering if the general method of avoiding non-termination can be
made to work in these more complex cases.

Incidentally, the constraint solver stack overflow problem can be
turned to our advantage. The typechecker's exhausting the stack should
be considered a failure to match the instance -- and so the
typechecker should mark the current instance inappropriate and try
another one, if any. I have just implemented this strategy in a logic
programming system I'm working on, and it works beautifully. I can
find counter-examples of Haskell instances violating functional
dependencies no matter in which order the instances are given.

	Thank you!