Non-type variable constraint

Question

I am trying to use the Parsec library to parse a list of Token values. I'd like to use the token function in Text.Parsec.Prim to match a single value. It seems like this should work:

type TokenParser a = Parsec [Token] () a

mytoken :: (Token -> Bool) -> TokenParser Token
mytoken test = token showTok posFromTok testTok
  where -- and so on

This gives a compile error:

No instance for (Stream [Token] Identity Token)
  arising from a use of `Prim.token'
Possible fix:
  add an instance declaration for (Stream [Token] Identity Token)

Okay, let's change the type declaration on mytoken:

mytoken :: Stream [Token] Identity Token => (Token -> Bool) -> TokenParser Token

This works, after we add the {-# LANGUAGE FlexibleContexts #-} extension.

What is going on? First of all, the Stream class definition in Text.Parsec.Prim has Monad m => Stream [tok] m tok as one of the instances. Shouldn't Stream [Token] Identity Token already be covered by that instance? Second, how is it that this is even constraining anything? There are no type variables to be constrained in the type of mytoken.

Worse yet, when I go to use my new, "constrained" mytoken in another function, I get exactly the same error, No instance for (Stream [Token] Identity Token) arising from... It actually necessitates putting the same, seemingly no-op type constraint on the type of the function trying to call mytoken.

If anyone can help explain to me what this type constraint is doing, I'd be very appreciative.

Answer 1

The following file is the minimal one I could construct that reproduces your problem. (In the future, you should create such a file yourself for us.)

import Text.Parsec.Prim

data Token

type TokenParser a = Parsec [Token] () a

mytoken :: (Token -> Bool) -> TokenParser Token
mytoken test = token showTok posFromTok testTok

showTok = undefined
posFromTok = undefined
testTok = undefined

Changing the import from Text.Parsec.Prim to Text.Parsec fixes the error. (The appropriate instance is defined in Text.Parsec.String, which is imported by Text.Parsec.Prim.) You also ask why this change makes it compile but not work:

mytoken :: Stream [Token] Identity Token => (Token -> Bool) -> TokenParser Token

The general rule is that the type "C => T" says: "you can use this thing as if it were a T, provided you can show that constraint C is satisfied". So giving mytoken the type you did says to wait until mytoken is used as if it were a plain old (Token -> Bool) -> TokenParser Token, and as soon as it is, try to discharge the obligation of showing that Stream [Token] Identity Token holds. Since you still haven't imported the appropriate instance, it can't discharge that obligation and complains.