[Haskell-cafe] looking for examples of non-full Functional Dependencies

[Martin Sulzmann]

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