[Haskell-cafe] looking for examples ofnon-fullFunctional
Dependencies
Tom Schrijvers
Tom.Schrijvers at cs.kuleuven.be
Thu Apr 17 14:11:44 EDT 2008
> 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/
More information about the Haskell-Cafe
mailing list