GHCI can't infer Eq class at compile time, but does fine at runtime?

Question

Sorry for the confusing title. I am writing a parser combinator library in Haskell for fun. Here are all (I think!) the relevant type annotations and 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 around to the current state, and if the parse is successful, wraps the result in an Either. The nil parser takes a state and returns a successful parse of the empty list. So we should have,

parse nil "dog" == Right []

In fact, if I just load the module where all these live, then it compiles and this evaluates to True.

I'm actually trying to run some QuickCheck tests on the library, though, so I wrote this:

import Parsimony
import Test.QuickCheck

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

This fails to compile! It throws the following error:

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

At this point I am mostly just confused why an expression could work fine when evaluated, but fail to compile in a parametrized version.

Answer 1

Since nil is polymorphic and Right [] is also polymorphic GHC has an expression of type Bool, but with some unbound type variable in the middle. GHC keels over and dies since it doesn't know what concrete type to use. GHCi for better or worse, will infer [()] or something like that because of its defaulting rules. This is one of ghci's weird quirks, it will automagically default type variables.

To fix this, simply for force the binding of a manually

-- It's 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 a parser library, good luck!

Answer 2

The problem is that the type of nil is Parser [a]. So parse nil xs is of type Either ParseError [a]. Right [] is most generally of type Either l [a]; comparing it to parse nil xs forces the l to be ParseError, but the type in the list is still completely unconstrained. Without any more context it remains fully polymorphic; that a isn't necessarily a member of the Eq type class and even if it is there's no way to know which instance to use for the implementation of ==, and so it isn't valid to invoke == on those two terms.

In a realistic program, you'd likely be saved from this by the fact that you'd use the result for something, which would force that particular occurrence to be consistent with whatever you use it for. That would probably be some concrete type which has an implementation of Eq.

When you talk about loading the module, I presume you mean in the GHCI interpreter. GHCI adds some additional defaulting rules. In particular it will tend to default unconstrained type variables (which aren't the type of a top level function) to (), so that it doesn't have to complain about ambiguous type variables quite so often.

An interactive session in GHCi tends to encounter ambiguous type variable far more often than realistic modules compiled in full, because it has to compile small snippets mostly independently. GHCi has extended defaulting rules to make those work a lot more often (though it often only delays the error to the next reference when the user was expecting a different type, and the difference between GHCi and GHC often causes confusion).

Test snippets can suffer from a similar problem. If you're testing polymorphic functions you often don't constrain some of the types sufficiently for type inference to work, as you would in real purposeful usage of the function. But without the extended defaulting rules of GHCi, this problem manifests as an actual ambiguous type error at the location of the problem, rather than masking it by arbitrarily picking a type.

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

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