GHCI cannot derive the Eq class at compile time, but works fine at runtime?

Question

Sorry for the confusing name. I am writing a library of parser combinators in Haskell for fun. Here are all (I think!) Relevant annotations and type definitions:

data Parser a = Parser (State -> Reply a) parse :: Parser a -> [Char] -> Either ParseError a nil :: Parser [a] nil = Parser $ \state -> Ok [] state 

Basically, the parse function applies the function that a Parser wraps to its current state, and if the parsing is successful, completes the result in Either . The nil parser takes state and returns a successful parsing of the empty list. So we must have,

 parse nil "dog" == Right [] 

In fact, if I just load the module in which they all live, it compiles and it evaluates to True.

I'm actually trying to run some QuickCheck tests in a library, so I wrote the following:

 import Parsimony import Test.QuickCheck prop_nil :: [Char] -> Bool prop_nil xs = parse nil xs == Right [] 

This will not compile! It produces the following error:

 No instance for (Eq a0) arising from a use of `==' The type variable `a0' is ambiguous 

At this point, I'm mostly confused about why the expression might work fine in evaluating, but not compiled in the parameterized version.

Answer 1

Since nil is polymorphic and Right [] also polymorphic to GHC, it has an expression of type Bool , but with some unrelated type variable in the middle. GHC keels and dies, as he does not know which particular type to use. GHCi is better or worse, will output [()] or something like that because of its default rules. This is one of ghci's odd quirks, it will automatically change by default.

To fix this, just to force a binding manually

 -- It important that whatever you force it to actually is comparable -- eg there should be an instance like instance Eq ParseError where -- Otherwise you're kinda stuck. prop_nil xs = parse nil xs == (Right xs :: Either ParseError String) 

PS I like the name Parsimony for the library of parsers, good luck!

Answer 2

The problem is that type nil is equal to Parser [a] . So parse nil xs is of type Either ParseError [a] . Right [] usually of type Either l [a] ; comparing it with parse nil xs makes l be a ParseError , but the type in the list is still not completely bounded. Without any context, it remains completely polymorphic; that a not necessarily a member of a class of type Eq , and even if there is no way to find out which instance will be used to implement == , and therefore it is not valid to call == in these two terms.

In a realistic program, you are likely to be saved from this by the fact that you are using the result for something that would make such a specific event compatible with what you are using it for. This will probably be the specific type that the Eq implementation has.

When you talk about loading a module, I assume you mean the GHCI interpreter. GHCI adds some additional default rules. In particular, he will tend to use variables of type unconstrined type (which are not a type of top-level function) to () , so he does not have to complain about ambiguous type variables so often.

An interactive session in GHCi tends to encounter an ambiguous type variable much more often than realistic modules compiled in its entirety, since it should make small fragments mostly independently. GHCi has expanded the default rules to make them work much more often (although often it only delays the error until the next link when the user expects a different type, and the difference between GHCi and GHC often causes confusion).

Test fragments may experience a similar problem. If you are testing polymorphic functions, you often do not limit some of the types sufficient to deduce the type to work, as in real purposeful use of the function. But without the GHCi’s extended default rules, this problem manifests itself as an actual ambiguous type error when posting the problem, rather than masking it by arbitrary type selection.

To fix this, you just need to add a type annotation to fix the list type. Either declare the full type parse nil xs , or Right [] , just declare the type of the empty list literal on the right side. Sometihng how this should do the trick:

 prop_nil :: [Char] -> Bool prop_nil xs = parse nil xs == Right ([] :: [Int]) 

Answer 3

Another way would be to avoid the Eq constraint in the first place:

 prop_nil xs = either (const False) null (parse nil xs) 

or, more explicit

 prop_nil xs = case parse nil xs of Right [] -> True _ -> False