To reuse a favorite word, I think that any implementation that distinguishes 'a -> b, a -> c' from 'a -> b c' is broken. :)<br>It does not implement FD, but something else. Maybe this something else is useful, but if one of the forms is strictly more powerful than the other then I don't see why you would ever want the less powerful one.<br>
<br> -- Lennart<br><br><div class="gmail_quote">On Thu, Apr 17, 2008 at 7:06 AM, Martin Sulzmann <<a href="mailto:martin.sulzmann@gmail.com">martin.sulzmann@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d">Mark P Jones wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Martin Sulzmann wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
We're also looking for (practical) examples of "multi-range" functional dependencies<br>
<br>
class C a b c | c -> a b<br>
<br>
Notice that there are multiple (two) parameters in the range of the FD.<br>
<br>
It's tempting to convert the above to<br>
<br>
class C a b c | c -> a, c -> b<br>
<br>
but this yields a weaker (in terms of type improvement) system.<br>
</blockquote>
<br>
I agree with Iavor.<br>
<br>
In fact, the two sets of dependencies that you have given here<br>
are provably equivalent, so it would be decidedly odd to have<br>
a "type improvement" system that distinguishes between them.<br>
<br>
</blockquote>
<br></div>
Consider<br>
<br>
class C a b c | a -> b, a -> c<br>
<br>
instance C a b b => C [a] [b] [b]<br>
<br>
Suppose we encounter the constraint<br>
<br>
C [x] y z<br>
<br>
What results can we expect from type improvement?<br>
<br>
1) Single-range non-full FDs in GHC following the FD-CHR formulation:<br>
<br>
The first FD C a b c | a -> b in combination with<br>
the instance head C [a] [b] [b] will yield<br>
<br>
C [x] y z improved by y = [b1] for some b1<br>
<br>
A similar reasoning yields<br>
<br>
C [x] y z improved by z = [b2] for some b2<br>
<br>
So, overall we get<br>
<br>
C [x] y z improved by y= [b1] and z = [b2]<br>
<br>
Unfortunately, we couldn't establish that b1 and b2 are equal.<br>
Hence, we can *not* apply the instance.<br>
<br>
2) Alternative design:<br>
<br>
We could now argue that the improvement implied by the FD<br>
is only applicable if we are in the "right" context.<br>
<br>
That is,<br>
C [x] y z doesn't yield any improvement because<br>
the context y is still underspecified (doesn't match<br>
the instance).<br>
<br>
In case of C [x] [y] z we get z = [y]<br>
(and C [x] z [y] yields z = [y])<br>
<br>
<br>
3) Multi-range FDs<br>
<br>
Consider<br>
<br>
class C a b c | a -> b c<br>
<br>
instance C a b b => C [a] [b] [b]<br>
<br>
This time it's straightforward.<br>
<br>
C [x] y z yields the improvement y = [b] and z = [b]<br>
which then allows us to apply the instance.<br>
<br>
4) Summary.<br>
<br>
With multi-range FDs we can derive "more" improvement.<br>
<br>
C [x] y z yields y = [b] and z = [b]<br>
<br>
Based on the FD-CHR formulation, for the single-range FD case we get<br>
<br>
C [x] y z yields y = [b1] and z = [b2]<br>
<br>
which is clearly weaker.<br>
<br>
The alternative design is even weaker, from C [x] y z we can derive<br>
any improvement.<br>
<br>
So, I conclude that in the Haskell type improvement context<br>
there's clearly a difference among single-range and multi-range FDs.<br>
<br>
Of course, we could define multi-range FDs in terms of single-range FDs<br>
which then trivially solves the "equivalence" problem (but some user<br>
may be disappointed that their multi-range FDs yield weaker improvement).<br>
<br>
Thanks for your pointers below but I believe that FDs in the Haskell context<br>
can be quite different from FDs in the database context.<br><font color="#888888">
<br>
- Martin</font><div class="Ih2E3d"><br>
<br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
While you're looking for unusual examples of fundeps, you<br>
might also want to consider things like:<br>
<br>
class C a b c | a -> b, b -> c<br>
<br>
Note that this is subtly different from a -> b c because<br>
<br>
{a -> b, b -> c} |= {a -> b c}<br>
<br>
while the reverse does not hold. Instead of type classes,<br>
I'll give you some more down-to-earth examples of relations<br>
that satisfy these dependencies:<br>
<br>
{Paper, Conference, Year}<br>
{Professor, University, Country}<br>
{Person, FavoriteFood, FoodGroup}<br>
...<br>
<br>
For further insight, you might want to take a look at the theory<br>
of relational databases to see how functional dependencies are<br>
used there. In that context, some sets of dependencies (such<br>
as {a -> b, b -> c}) can be interpreted as indicators of bad<br>
design. This, in turn, might give you some ideas about the kinds<br>
of dependencies you can expect to encounter in well-designed<br>
Haskell code. (Of course, you might still find examples in other<br>
Haskell code of dependencies that would make a database person<br>
wince :-)<br>
<br>
</blockquote>
<br></div><div><div></div><div class="Wj3C7c">
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br>