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

Iavor Diatchki wrote:

Hello,

On Wed, Apr 16, 2008 at 11:06 PM, Martin Sulzmann 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