FD problem in GHC 6.6
Fellow Haskellers, I have a package that uses some light typeclass hackery to automaticly build parsing algorithms based on the type of a function. I was recently informed that my package doesn't compile on GHC 6.6 due to the new restrictions on FD resolution; in particular I have instance declarations which fail the coverage condition. I can use undecidable instances to make the package compile again, but I'd prefer not to if I can avoid it. Are there any easy tricks I can use to make this work? I only sort-of understand the new restrictions, so I'm at something of a loss as to how to work around them. The problem is fairly isolated in my code: the affected section begins at line 140 in http://www.eecs.tufts.edu/~rdocki01/shellac/src/System/Console/Shell/Command... I've reproduced the class and a few of the instance declarations here: class CommandFunction f st | f -> st where parseCommand :: String -> f -> CommandParser st commandSyntax :: f -> [Doc] instance CommandFunction (Sh st ()) st where parseCommand wbc m str = -- list monad do (x,[]) <- runRegex (maybeSpaceBefore (Epsilon (CompleteParse m))) str return x commandSyntax _ = [] instance CommandFunction r st => CommandFunction (Int -> r) st where parseCommand = doParseCommand Nothing intRegex id commandSyntax f = text (show intRegex) : commandSyntax (f undefined) instance CommandFunction r st => CommandFunction (Integer -> r) st where parseCommand = doParseCommand Nothing intRegex id commandSyntax f = text (show intRegex) : commandSyntax (f undefined) -- Robert robdockins@fastmail.fm -- http://www.fastmail.fm - IMAP accessible web-mail
instance CommandFunction (Sh st ()) st where ^ I think your first argument (on which the second has a functional dependence) does not determine the second argument, since it makes use of st in the first argument. This strikes me as a likely place to begin.
Dan Robert wrote:
Fellow Haskellers,
I have a package that uses some light typeclass hackery to automaticly build parsing algorithms based on the type of a function.
I was recently informed that my package doesn't compile on GHC 6.6 due to the new restrictions on FD resolution; in particular I have instance declarations which fail the coverage condition. I can use undecidable instances to make the package compile again, but I'd prefer not to if I can avoid it. class CommandFunction f st | f -> st where parseCommand :: String -> f -> CommandParser st commandSyntax :: f -> [Doc]
instance CommandFunction (Sh st ()) st where
parseCommand wbc m str = -- list monad do (x,[]) <- runRegex (maybeSpaceBefore (Epsilon (CompleteParse m))) str return x
commandSyntax _ = []
instance CommandFunction r st => CommandFunction (Int -> r) st where parseCommand = doParseCommand Nothing intRegex id commandSyntax f = text (show intRegex) : commandSyntax (f undefined)
instance CommandFunction r st => CommandFunction (Integer -> r) st where parseCommand = doParseCommand Nothing intRegex id commandSyntax f = text (show intRegex) : commandSyntax (f undefined)
On Dec 19, 2006, at 10:11 PM, Dan Weston wrote:
instance CommandFunction (Sh st ()) st where ^ I think your first argument (on which the second has a functional dependence) does not determine the second argument, since it makes use of st in the first argument. This strikes me as a likely place to begin.
No, I'm pretty sure this isn't a problem. The second argument is determined _because_ it is mentioned in the first. The functional dependencies and instance declarations work, as long as I can make the compiler accept them. They are only being rejected by the termination-checking part of the algorithm. That said, I'm open to the idea of reformulating these instances. In fact, I don't really like the fact that I need FDs. It seems to me that I should somehow be able to eliminate the second argument altogether and thus the FD, but I can't seem to figure it out.
Dan
Robert wrote:
Fellow Haskellers, I have a package that uses some light typeclass hackery to automaticly build parsing algorithms based on the type of a function. I was recently informed that my package doesn't compile on GHC 6.6 due to the new restrictions on FD resolution; in particular I have instance declarations which fail the coverage condition. I can use undecidable instances to make the package compile again, but I'd prefer not to if I can avoid it. class CommandFunction f st | f -> st where parseCommand :: String -> f -> CommandParser st commandSyntax :: f -> [Doc] instance CommandFunction (Sh st ()) st where
parseCommand wbc m str = -- list monad do (x,[]) <- runRegex (maybeSpaceBefore (Epsilon (CompleteParse m))) str return x commandSyntax _ = [] instance CommandFunction r st => CommandFunction (Int -> r) st where parseCommand = doParseCommand Nothing intRegex id commandSyntax f = text (show intRegex) : commandSyntax (f undefined) instance CommandFunction r st => CommandFunction (Integer -> r) st where parseCommand = doParseCommand Nothing intRegex id commandSyntax f = text (show intRegex) : commandSyntax (f undefined)
Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG
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
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
participants (4)
-
Dan Weston -
Iavor Diatchki -
Robert -
Robert Dockins