There are three (relevant) places a constraint could go:
data Typeable a => Exp a = ... -- (1)
data Exp a where
ReadFirstVar :: Typeable a => Exp a -- (2)
eval :: Typeable a => Exp a -> ... -- (3)
You're currently doing (2). When people talk about not putting constraints on datatypes, I imagine they're talking about (1), which is indeed a bad idea. Using (1) essentially buys you nothing -- you would still still a constraint like (3) to work with the type declared in (1). So, the real choice is between (2) and (3). Each of these has its advantages. (2) essentially says that the data stored by the ReadFirstVar constructor is the type of the expression. (3) essentially says that any caller of `eval` also has to pass in the desired type for the expression. Without seeing more code, it's hard to know what's better in your scenario.
But, my bottom line is that the advice you've read probably pertains to (1), not (2) -- it's not saying that what you've done is bad.
Richard
Ugly, maybe not, but I read somewhere that the class restriction should be on the functions definitions than in the datatype definition... That is, the datatype is usually defined without class restriction, instead the necessary class restriction is added latter on in the functions signatures that work on that datatype.