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
Thanks. This is the kind of solution I was looking for. The problem is, when I try to access the "hidden" Expr type the compiler complains: Couldn't match type `a1' with `a' `a1' is a rigid type variable bound by a pattern with constructor ExprE :: forall a. Expr a -> ExprE, in an equation for `withExprE' `a' is a rigid type variable bound by the type signature for withExprE :: ExprE -> (Expr a -> r) -> r