Are fundeps the right model at all?
Marcin 'Qrczak' Kowalczyk
qrczak@knm.org.pl
15 Jan 2001 19:49:05 GMT
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