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

[Martin Sulzmann]

Iavor Diatchki wrote:
> Hello,
>
> On Thu, Apr 17, 2008 at 10:26 AM, Martin Sulzmann
> <martin.sulzmann at gmail.com> 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