Iavor Diatchki wrote:
Hello,
On Thu, Apr 17, 2008 at 10:26 AM, Martin Sulzmann
<[EMAIL PROTECTED]> 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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
