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

[Martin Sulzmann]

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