[Haskell-beginners] Problem with GADTs and Parsec

[Brent Yorgey]

On Sat, Feb 08, 2014 at 08:10:18PM +0100, Lorenzo Tabacchini wrote:
> 
> exprParser :: Parsec String u (Expr a)
> exprParser = parens exprParser
>  <|> (reserved "true" >> return (Bool True))
>  <|> (reserved "false" >> return (Bool False))
>  <|> (stringLiteral >>= return . Text)

As Brandon explained, this type does not mean what you want: it
promises to be able to return *any* type of Expr, but then it goes and
tries to return *particular* types of Exprs.  Of course, the type is a
lie: you will only be able to return specific types of Exprs, but you
can't know which ones in advance.

In my opinion, this is one of the few places where existential
wrappers are really what you want.  If I were you, I would do
something like this:

  data ExprE where
    ExprE :: Expr a -> ExprE   -- existentially hides the expression type

Now you can write your parser to return an ExprE, with the type of the
expression hidden inside. In order to be able to use the resulting
ExprE values, you will also want a function like

  withExprE :: ExprE -> (Expr a -> r) -> r
  withExprE (ExprE expr) k = k expr

-Brent