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

Iavor Diatchki iavor.diatchki at gmail.com
Thu Apr 17 14:13:54 EDT 2008


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
  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!


More information about the Haskell-Cafe mailing list