Existential quantification parser signature

Question

In the beginning, I had a simple type for the parser:

data Parser a = Parser ([Token] -> Either String (a, [Token])) 

I use Either for error messages on the left side and the parsed expression with the remaining tokens on the right side.

This function "unpacks" the parser function.

 parse :: Parser a -> [Token] -> Either String (a, [Token]) parse (Parser p) = p 

My goal was to make Parser more general, that it not only accepts tokens as input. Therefore, I used the pragma ExistentialQuantification and changed it to:

 data Parser a = forall b. ([b] -> Either String (a, [b])) 

I want to know: what type performs the parsing function?

I could not understand, and this is impossible to do. GHCi gave this error:

 Couldn't match type `t' with `[b] -> Either String (t1, [b])' `t' is a rigid type variable bound by the inferred type of parse :: Parser t1 -> t at ParserCombinator.hs:9:1 In the expression: p In an equation for `parse': parse (Parser p) = p 

Thanks for your help.

EDIT: Thank you very much for your answers.

The reason I wanted the type to look like "Parser a" is because I saw it in other parsing libraries, like parsec. But now I saw that this is just a shorthand for parsers that take strings as input.

It makes sense to use "data parser ba". This was what I also tried before, but then I had a weird error in the monad instance for my parser, because instead I wrote Parser ab data:

 import Control.Monad.Error data Parser ab = Parser ([b] -> Either String (a, [b])) parse (Parser p) = p instance Monad (Parser x) where p >>= f = Parser (\tokens -> do (parsed, rest) <- parse p tokens parse (f parsed) rest) return a = Parser (\ts -> Right (a, ts)) fail b = Parser (\_ -> Left b) 

He gives this error:

 ParserCombinator.hs:12:18: Couldn't match type `x' with `b' `x' is a rigid type variable bound by the instance declaration at ParserCombinator.hs:9:24 `b' is a rigid type variable bound by the type signature for >>= :: Parser xa -> (a -> Parser xb) -> Parser xb at ParserCombinator.hs:10:5 Expected type: a Actual type: x In the first argument of `f', namely `parsed' In the first argument of `parse', namely `(f parsed)' In a stmt of a 'do' block: parse (f parsed) rest ParserCombinator.hs:12:26: Couldn't match type `a' with `b' `a' is a rigid type variable bound by the type signature for >>= :: Parser xa -> (a -> Parser xb) -> Parser xb at ParserCombinator.hs:10:5 `b' is a rigid type variable bound by the type signature for >>= :: Parser xa -> (a -> Parser xb) -> Parser xb at ParserCombinator.hs:10:5 Expected type: [b] Actual type: [a] In the second argument of `parse', namely `rest' In a stmt of a 'do' block: parse (f parsed) rest ParserCombinator.hs:13:38: Couldn't match type `a' with `x' `a' is a rigid type variable bound by the type signature for return :: a -> Parser xa at ParserCombinator.hs:13:5 `x' is a rigid type variable bound by the instance declaration at ParserCombinator.hs:9:24 In the expression: a In the first argument of `Right', namely `(a, ts)' In the expression: Right (a, ts) 

Why does this work if you use Parser ba instead of Parser ab? And why do I need this x in Parser x? What does it contain? It would be nice if you could give an example for another instance of the monad where this variable is used.

Answer 1

You mean

 data Parser a = forall b. Parser ([b] -> Either String (a, [b])) 

What this actually means becomes clearer if you write existential in your stricter GADT notation:

 data Parser a where Parser :: forall b. ([b] -> Either String (a, [b])) -> Parser a 

i.e. the Parser constructor is a universally-quantized function that takes a parser ([b] -> ... but always returns a Parser a that knows nothing about which particular b should be used internally. Therefore, it is useless: you cannot provide a list tokens b if you do not know what type should really be!

To make it concrete: parse will be the opposite of Parser ; which swaps the quantifiers, so this will be an existential function (duh)

 parse :: exists b . Parser a -> ([b] -> Either String (a, [b])) 

Now this type does not exist in Haskell, but it is equivalent to universal arguments:

 parse :: Parser a -> ((forall b . [b]) -> Either String (a, exists b . [b])) 

At this point, it is clear that you cannot use it in any meaningful way: the only inhabitants of forall b. [b] forall b. [b] are [] and undefined (and, as Tikhon Gelvis notes, [undefined] , [undefined, undefined] , [undefined, undefined, undefined] , etc.).

---

I'm not sure what you are actually going to do with this type, but the existential approach is definitely not suitable. You should probably do

 data Parser ba = Parser ([b] -> Either String (a, [b]))