[Haskell-cafe] looking for examples of non-full Functional
Dependencies
Martin Sulzmann
martin.sulzmann at gmail.com
Thu Apr 17 13:26:41 EDT 2008
Iavor Diatchki wrote:
> Hello,
>
> On Wed, Apr 16, 2008 at 11:06 PM, Martin Sulzmann
> <martin.sulzmann at gmail.com> wrote:
>
>> 3) Multi-range FDs
>>
>> Consider
>>
>> class C a b c | a -> b c
>>
>> instance C a b b => C [a] [b] [b]
>>
>> This time it's straightforward.
>>
>> C [x] y z yields the improvement y = [b] and z = [b]
>> which then allows us to apply the instance.
>>
>
> I don't think that this improvement rule is justified (unless there
> are some assumptions that are added to the system that go beyond FD?).
> By the way, note that the above example does not have any instances
> for C, so lets first add a base case like this:
>
> instance C Char Bool Bool
>
> Now the instances for C are: { C Char Bool Bool, C [Char] [Bool]
> [Bool], ... }. Certainly, if you just consider these instances, then
> the improvement rule that you suggest is valid. However, suppose that
> we also add the instance:
>
> instance C [Int] Char Bool
>
> Note that this instance does not violate the FD: if we know the first
> argument, then we know exactly what are the other two arguments. In
> this context, it is not OK to improve C [x] y z as you suggest because
> 'x' may be instantiate to 'Int'
>
There possible points of view here.
Consider a -> b c as a short-hand for a -> b, a -> c. That's fine.
But we may also want to go beyond (single-range) FDs. That's why I have
in mind.
Therefore, a -> b, a -> c is a short-hand for a -> b, c.
(At least there's one supporter, Ganesh, assuming that Tom and I are
neutral :) )
Suppose we encode the multi-range FD a -> b, c as defined in the FD-CHR
paper.
Then,
class C a b c | a -> b c
instance C a b b => C [a] [b] [b]
instance C [Int] Char Bool
leads to an instance improvement/instance improvement conflict,
like in the single-range FD case
class D a b | a -> b
instance D a a => D [a] [a]
instance D [Int] Char
All of the above design choices make sense. There's no right or wrong.
But it's wrong to simply ignore possible FD variants which go beyond
single-range FDs.
Martin
More information about the Haskell-Cafe
mailing list