[Haskell-cafe] FD problem in GHC 6.6

Iavor Diatchki iavor.diatchki at gmail.com
Wed Dec 20 12:45:34 EST 2006


Hi,
I don't have a solution for you problem (besides using undecidable
instances) but I can explain the "coverage condition".

On 12/19/06, Robert <robdockins at fastmail.fm> wrote:
> class CommandFunction f st | f -> st where
>   parseCommand  :: String -> f -> CommandParser st
>   commandSyntax :: f -> [Doc]

The functional dependency on this class adds the following axiom
(improvement rule) :
improve (CommandFunction f st1, CommandFunction f st2) using st1 = st2

Before accepting an instance, an implementation needs to check that
the instance will not violate this rule (i.e., the functional
dependency is satisfied).  In general, this may be difficult to check.
 The "coverage condition" (CC) is a (conservative) rule that
guarantees that the functional dependency is satisfied.  It states
that an instance is accepted if all type variables in the determined
types are mentioned in the determining types.  The rule is
conservative because (as you have noticed) there are cases when the FD
axiom is not violated but the rule rejects an instance.    Examples:

> instance CommandFunction (Sh st ()) st where
>   parseCommand wbc m str = ...

This instance satisfies the CC because "st" is mentioned in "Sh st ()".

> instance CommandFunction r st
>       => CommandFunction (Int -> r) st where ...

This instance does not satisfy the CC because "st" is not mentioned in
"Int -> r".

> instance CommandFunction r st
>       => CommandFunction (Integer -> r) st where ...

This instance does not satisfy the CC because "st" is not mentioned in
"Integer -> r".

Hope this helps.
-Iavor


More information about the Haskell-Cafe mailing list