[Haskell-cafe] looking for examples ofnon-fullFunctional Dependencies

[Tom Schrijvers]

> a little more experimentation leaves me confused. consider
>
> [4]
>   class C a b c | a -> b -- , a -> c
>   instance C a b b => C [a] [b] [b]
>
>   Hugs:
>   :t undefined :: C [x] y z => (x,y,z)
>   undefined :: C [a] [b] c => (a,[b],c)
>
>   GHCi:
>   :t undefined :: C [x] y z => (x,y,z)
>   undefined :: C [x] y z => (x,y,z) :: (C [x] [b] z) => (x, [b], z)
>
> both systems improve 'y' to '[b]', but not to '[b] where z=[b]'.
>
> ok, the third parameter is not in range of an FD, so cannot be
> instantiated by improvement, and without that, 'y' cannot be
> instantiated as far as the FD would suggest. it is slightly
> surprising that 'y' get partially instantiated at this stage.

My understanding of an FD a -> b is to improve, or in other words 
instantiate, b as much as possible based on information from a.

With C [x] y z we know for sure that y must be [b] for some b. Improvement 
adds (propagates) this information we know for sure. With our limited 
information, we may not know what b is, but just knowing the list type 
constructor [] may already be useful. For instance, if we had a 
second type class constraint D y for which there is an instance

 	instance D [a] where ...

Then inferring that y = [b] will allow us to figure out that we can use 
the above instance for it.

> however, if we try to help the process along by instantiating
> 'z' to '[b]' ourselves, we get:
>
> [5]
>   Hugs:
>   :t undefined :: C [x] y [b] => (x,y,[b])
>   undefined :: C [a] [b] [c] => (a,[b],[c])
>
>   GHCi:
>   :t undefined :: C [x] y [b] => (x,y,[b])
>   undefined :: C [x] y [b] => (x,y,[b]) :: (C [x] [b1] [b]) => (x, [b1], 
> [b])
>
> i would have expected 'C a c c => (a,[c],[c])' here, as
> only instantiation of 'y' is required; so my intuition is still off,
> and neither [A] nor [B] seems to capture Hugs' interpretation.

You did not provide the FD a -> c (or even a -> b c). That means that you 
did not allow the type checker to improve c based on a. Nor did you 
provide the FD a c -> b. For that reason the type checker does not use any 
information from the third parameter to improve the second parameter.

It does indeed feel somewhat strange, because there is no alternative for 
y (except if you allow overlapping instances and add e.g. an instance C 
[a] [b] [Int]).

Cheers,

Tom

--
Tom Schrijvers

Department of Computer Science
K.U. Leuven
Celestijnenlaan 200A
B-3001 Heverlee
Belgium

tel: +32 16 327544
e-mail: tom.schrijvers at cs.kuleuven.be
url: http://www.cs.kuleuven.be/~toms/