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

Iavor Diatchki wrote:

Hello,

On Wed, Apr 16, 2008 at 8:06 AM, 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.

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