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

[Lennart Augustsson]

To reuse a favorite word, I think that any implementation that distinguishes
'a -> b, a -> c' from 'a -> b c' is broken. :)
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.

  -- Lennart

On Thu, Apr 17, 2008 at 7:06 AM, Martin Sulzmann <martin.sulzmann at gmail.com>
wrote:

> 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 :-)
> >
> >
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080417/253a67a5/attachment.htm