Are fundeps the right model at all?

Marcin 'Qrczak' Kowalczyk
9 Jan 2001 18:52:11 GMT

Mon, 8 Jan 2001 17:53:35 +1300, Tom Pledger <> pisze:

>  > Having types with type variables which are never instantiated nor
>  > constrained should be equivalent to having ground types!
> Do you have any examples of such a type variable in an instance decl?

Now I have a practical example where fundeps don't work and keys
would work - but the type variable is later instantiated.

Let's take Parsec from ghc's libraries which includes the following
(this is cut down):

data TokenParser = TokenParser {
    identifier :: Parser String,
    reserved   :: String -> Parser (),
    operator   :: Parser String,
    reservedOp :: String -> Parser (),
    parens     :: forall a. Parser a -> Parser a}

makeTokenParser:: LanguageDef -> TokenParser

I would like to express this "first-class module" in my records
proposal, to make it extensible (there can be different types similar
to TokenParser with similar fields and used polymorphically together
with TokenParser).

Each record field in my proposal induces a class:
    class Has_field r a | r -> a where
        get_field :: r -> a

The fundep, or something which allows to find the instance from the
type of the record only, is required to make this practical. A type
which includes Has_field r a in its context, and includes r but not a
in its body, is legal.

For non-polymorphic fields it works great. But parens cause trouble:
    instance Has_parens TokenParser (Parser a -> Parser a)
This instance is illegal because of the fundep. What it should mean is:
    instance Has_parens TokenParser (forall a. Parser a -> Parser a)
but this is not possible either.

With keys instead of fundeps it works! The first instance is OK.
The record type is specified to be a key in all Has_field classes,
meaning that the record type alone is sufficient to determine which
instance of a field getter to use.

It is not always sufficient to determine the exact type of the field,
but this is not needed. For example here many types are good because
the instance is polymorphic wrt. a type variable used in the field's

I want keys instead of fundeps! :-)

 __("<  Marcin Kowalczyk *
  ^^                      SYGNATURA ZASTĘPCZA