Are fundeps the right model at all?

[Marcin 'Qrczak' Kowalczyk]

Thanks for the reply!

Mon, 15 Jan 2001 02:01:18 -0800, Mark P Jones <mpj@cse.ogi.edu> pisze:

> 1) "A weaker notion of ambiguity" (title of Section 5.8.3 in my dissertation,
>    which is where I think the following idea originated):  We can modify the
>    definition of ambiguity for certain kinds of class constraint by considering
>    (for example) only certain subsets of parameters.  In this setting, a type
>    P => t is ambiguous if and only if there is a variable in AV(P) that is not
>    in t.  The AV function returns the set of potentially ambiguous variables in
>    the predicates P.  It is defined so that AV(Eq t) = TV(t), but also can
>    accommodate things like AV(Has_field r a) = TV(r).  A semantic justification
>    for the definition of AV(...) is needed in cases where only some parameters
>    are used; this is straightforward in the case of Has_field-like classes.
>    Note that, in this setting, the only thing that changes is the definition
>    of an ambiguous type.

This is exactly what I have in mind.

Perhaps extended a bit, to allow multiple values of AV(P). During
constraint solving unambiguous choices for the value of AV(P) must
unify to a common answer, but ambiguous choices are not considered
(or something like that).

I don't see a concrete practical example for this extension yet, so
it may be an unneeded complication, but I can imagine two parallel
sets of types with a class expressing a bijection between them:
a type from either side is enough to determine the other. This is
what fundeps can do, basic (1) cannot, but extended (1) can - with a
different treatment of polymorphic types than fundeps, i.e. allowing
some functions which are not necessarily bijections.

> - When a user writes an instance declaration:
> 
>     instance P => C t1 ... tn where ...
> 
>   you treat it, in the notation of (2) above, as if they'd written:
> 
>     instance P => C t1 ... tn 
>      improves C t11 ... t1n, ..., C tm1 ... tmn where ...
> 
>   Here, m is the number of keys, and:  tij =  ti,   if parameter i is in key j
>                                            =  ai,   otherwise
>   where a1, ..., an are distinct new variables.

Sorry, I don't understand (2) well enough to see if this is the case.
Perhaps it is.

> - Keys will not give you the full functionality of functional dependencies,
>   and that missing functionality is important in some cases.

And vice versa. Plain fundeps can't allow both
    Has_parens r a => r
as an unambiguous type and
    Has_parens TokenParser (Parser a -> Parser a)
as an instance.

> PS. If we're going to continue this discussion any further, let's
> take it over into the haskell-cafe ...

OK.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK