Problem with functional dependencies

Jeffrey R. Lewis
Thu, 21 Dec 2000 00:59:29 -0800

Simon Peyton-Jones wrote:

> I think you can simplify the example.  Given
>         class HasFoo a b | a -> b where
>           foo :: a -> b
>         instance HasFoo Int Bool where ...
> Is this legal?
>         f :: HasFoo Int b => Int -> b
>         f x = foo x
> You might think so, since
>         HasFoo Int b => Int -> b
> is a substitution instance of
>         HasFoo a b => a -> b

This is the step where the reasoning goes wrong.  The functional dependency tells you that `b' isn't really a free variable, since it is dependent on `a'.  If you substitute for `a', you can't expect `b' to remain unconstrained.

Hugs complains that the inferred type for `f' is not general enough.  It's right to complain, but the real problem is that the signature is too general.  Asimilar situation arises if you try to declare an instance `HasFoo Int b', but in this case, hugs complains that the instance is more general than the dependency allows.  A useful thing to do would be to check for this sort of thing in signatures as well, so that the more appropriate error message can be given.