overlapping instances and functional dependencies

[Wolfgang Jeltsch]

I wrote on Saturday, 2003-08-09, 01:32, CEST:
> Hello,
>
> I have this code:
>     class C a b c | a b -> c where
>         f :: a -> b -> c
>
>     instance C a b c => C a (x,y,b) c where
>         f a (_,_,b) = f a b
>
>     instance C a (a,c,b) c where
>         f _ (_,c,_) = c
> ghci -fglasgow-exts -fallow-overlapping-instances compiles it without
> complaint but hugs -98 +o says:
>     ERROR "ClassProblem.hs":7 - Instances are not consistent with
>     dependencies
>     *** This instance    : C a (a,b,c) b
>     *** Conflicts with   : C a (b,c,d) e
>     *** For class        : C a b c
>     *** Under dependency : a b -> c
> Can anyone tell me what the reason for this is and, maybe, how to avoid
> these problems with Hugs?
>
> Wolfgang

Hal Daume answered on Saturday, 2003-08-09, 01:53, CEST:
> Suppose somewhere we have an instance:
>
>  instance C Int Bool Int
>
> when the first instance decl you have says we also have
>
>   instance C Int (x,y,Bool) Int
>
> in this case, Int + (x,y,Bool) should uniq. specify Int.
>
> however, we also have:
>
>   instance C a (a,c,b) c
>
> where, if we let a=Int, b=Bool, c=Char, then we get that
>   Int + (Int,Char,Bool) should uniq. specify Char.
>
> these two confict because if, in the first case, we instantiate x to Int and
> y to Char, then one says that the third param should be a Bool and the other
> says the third param should be a Char.
>
> (or at least this is my understanding -- someone might correct me)
>
>  - Hal

Hello,

I wouldn't suppose that there is a conflict in your example. The question is 
for which t there is an instance C Int (Int,Char,Bool) t. There are two 
competing instance declarations:
    (1) instance C a b c => C a (x,y,b) c [...]
        Because in your example there is an instance C Int Bool Int we would
        get the instance C Int (Int,Char,Bool) Int.
    (2) instance C a (a,c,b) c [...]
        This clearly votes for C Int (Int,Char,Bool) Char.
But the second instance declaration is more specific. In the first one we have 
the "pattern" "arbitrary type - triple type - arbitrary type" with no further 
restrictions. In the second one we have the same "pattern" but with the 
restriction that the first parameter must equal the type of the first triple 
element and the third parameter must equal the type of the second triple 
element. Because of the handling of overlapping instances, the compiler 
should take the second instance declaration and deduce the instance C Int 
(Int,Char,Bool) Char.

What's wrong with my interpretation?

Wolfgang