typeclass relations

[S.M.Kahrs]

[snip]
> instance Foo Int where
>   foo =3D show
> =

> instance Bar Int where
>   bar a =3D (show a) ++ " bar!"
> =

> instance Foo Char where
>   foo =3D show
> =

> instance Foo a =3D> Bar a where
>   bar =3D foo

Notice: this last instance derives another instance of Bar Int, etc.

> If I try to compile this via GHC it complains loudly unless I feed it
> "-fglasgow-exts -fallow-undecidable-instances =

> -fallow-overlapping-instances", in which case it seems to do the right
> thing.  However, the warnings (and the names of the flags - "undecidabl=
e
> instances" doesn't sound good) make me nervous, and confused.  Why is
> there a problem with saying "every instance of Foo is also an instance =
of
> Bar, and here's how"?

The problem is the sublanguage in which you are working.
The class constraint simplification starts fairly simply (oh well)
in Haskell, but the more powerful you make it the more powerful
is the engine that does the job. Eventually you have full-blown
Prolog programming at that level, and hence undecidability.

The class checker for the above is like a little Prolog program:

foo(int).
bar(int).
foo(char).
bar(X) :- foo(X).

---
Stefan Kahrs