Mark P Jones wrote:
Martin Sulzmann wrote:
We're also looking for (practical) examples of "multi-range" functional dependencies
class C a b c | c -> a b
Notice that there are multiple (two) parameters in the range of the FD.
It's tempting to convert the above to
class C a b c | c -> a, c -> b
but this yields a weaker (in terms of type improvement) system.
I agree with Iavor.
In fact, the two sets of dependencies that you have given here are provably equivalent, so it would be decidedly odd to have a "type improvement" system that distinguishes between them.
Consider class C a b c | a -> b, a -> c instance C a b b => C [a] [b] [b] Suppose we encounter the constraint C [x] y z What results can we expect from type improvement? 1) Single-range non-full FDs in GHC following the FD-CHR formulation: The first FD C a b c | a -> b in combination with the instance head C [a] [b] [b] will yield C [x] y z improved by y = [b1] for some b1 A similar reasoning yields C [x] y z improved by z = [b2] for some b2 So, overall we get C [x] y z improved by y= [b1] and z = [b2] Unfortunately, we couldn't establish that b1 and b2 are equal. Hence, we can *not* apply the instance. 2) Alternative design: We could now argue that the improvement implied by the FD is only applicable if we are in the "right" context. That is, C [x] y z doesn't yield any improvement because the context y is still underspecified (doesn't match the instance). In case of C [x] [y] z we get z = [y] (and C [x] z [y] yields z = [y]) 3) Multi-range FDs Consider class C a b c | a -> b c instance C a b b => C [a] [b] [b] This time it's straightforward. C [x] y z yields the improvement y = [b] and z = [b] which then allows us to apply the instance. 4) Summary. With multi-range FDs we can derive "more" improvement. C [x] y z yields y = [b] and z = [b] Based on the FD-CHR formulation, for the single-range FD case we get C [x] y z yields y = [b1] and z = [b2] which is clearly weaker. The alternative design is even weaker, from C [x] y z we can derive any improvement. So, I conclude that in the Haskell type improvement context there's clearly a difference among single-range and multi-range FDs. Of course, we could define multi-range FDs in terms of single-range FDs which then trivially solves the "equivalence" problem (but some user may be disappointed that their multi-range FDs yield weaker improvement). Thanks for your pointers below but I believe that FDs in the Haskell context can be quite different from FDs in the database context. - Martin
While you're looking for unusual examples of fundeps, you might also want to consider things like:
class C a b c | a -> b, b -> c
Note that this is subtly different from a -> b c because
{a -> b, b -> c} |= {a -> b c}
while the reverse does not hold. Instead of type classes, I'll give you some more down-to-earth examples of relations that satisfy these dependencies:
{Paper, Conference, Year} {Professor, University, Country} {Person, FavoriteFood, FoodGroup} ...
For further insight, you might want to take a look at the theory of relational databases to see how functional dependencies are used there. In that context, some sets of dependencies (such as {a -> b, b -> c}) can be interpreted as indicators of bad design. This, in turn, might give you some ideas about the kinds of dependencies you can expect to encounter in well-designed Haskell code. (Of course, you might still find examples in other Haskell code of dependencies that would make a database person wince :-)