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

Dan Weston westondan at imageworks.com
Wed Apr 16 14:05:24 EDT 2008

Iavor Diatchki wrote:
> Hello,
> On Wed, Apr 16, 2008 at 8:06 AM, Martin Sulzmann
> <martin.sulzmann at gmail.com> 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.
> Could you elaborate on this?  I think that a system that distinguishes
> these two would be very confusing.   If you think of the FDs as
> logical statements about what is known of type variables, then the FDs
> on the two classes correspond to equivalent logical statements, so I
> am not sure why would we distinguish them for improvement purposes.
> Also, it seems fairly easy to convert between the two forms purely
> based on syntax, so if the one somehow results in better improvements,
> why would we ever use the other one?

The two are not isomorphic. The first one c -> a b contains an explicit 
order (class parameter order is significant), whereas the second does 
not (the FDs form a set). I think the isomorphic functional dependency 
in the first case would be the set of all FDs under permutation of class 
parameters, in this case: c -> a b, c -> b a

> As for examples of interesting uses of functional dependencies,
> perhaps the literature on relational databases would provide some?

Elaborating on the relational connection, it seems at first blush that

class C a b c | a -> b

is not ideally normalized and might presumably be profitably broken up into

class A a b | a -> b
class A a b => B a b c

More information about the Haskell-Cafe mailing list