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

Iavor Diatchki wrote:

Hello,

On Thu, Apr 17, 2008 at 10:26 AM, Martin Sulzmann wrote:

...

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

Sorry to be picky but there is no violation of the FD here. Note that the class D has only a single ground instance and to violate an FD you need at least two. As in the previous example, we can add an instance like this:

instance D Char Char

This results in more ground instances: { D [Int] Char, D Char Char, D [Char] [Char], ... } but again, there is no violation of the FD.

I think that a lot of the confusion in discussions such as this one (and we've had a few of those :-) stems from the fact that the term "functional dependency" seems to have become heavily overloaded. Often, the basic concept is mixed with (i) concepts related to checking that the basic concept holds (e.g., various restrictions on instances, etc), (ii) concepts related to how we might want to use the basic concept (e.g., what improvement rules to use). Of course, (i) and (ii) are very important, and there are a lot possible design choices. However, a number of the discussions I have seen go like this: 1) In general, it is hard to check if instances violate the stated functional dependencies. 2) So we have more restrictive rules, that are easier to check. 3) These more restrictive rules give us stronger guarantees, so we have more opportunity for improvement. While there is nothing inherently wrong with this, it is important to note that the extra improvement is not a result of the use of FDs but rather, from the extra restrictions that we placed on the instances. I think that this distinction is important because (i) it avoids mixing concepts, and (ii) points to new things that we may want to consider. For example, I think that there is an opportunity for improvement in situations where is class is not exported from a module. Then we know the full set of instances for the class, and we may be able to compute improvement rules.

Hope this helps! -Iavor

Can you pl specify the improvement rules for your interpretation of FDs. That would help! I'm simply following Mark Jones' style FDs. Mark's ESOP'00 paper has a consistency condition: If two instances match on the FD domain then the must also match on their range. The motivation for this condition is to avoid inconsistencies when deriving improvement rules from instances. For class D a b | a -> b instance D a a => D [a] [a] instance D [Int] Char we get D [a] b ==> b =[a] D [Int] b ==> b=Char In case of D [Int] b we therefore get b=Char *and* b =[a] which leads to a (unification) error. The consistency condition avoids such situations. The beauty of formalism FDs with CHRs (or type functions/families) is that the whole improvement process becomes explicit. Of course, it has to match the programmer's intuition. See the discussion regarding multi-range FDs. Martin