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

Mark P Jones mpj at cs.pdx.edu
Wed Apr 16 23:49:10 EDT 2008

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.

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 :-)

All the best,

More information about the Haskell-Cafe mailing list