GADT for polymorphic list

Question

I am parsing a few statements of the form

v1 = expression1
v2 = expression2
...

I am using the State Monad and my state should be a pair of (String, Expr a), I really insist on having the expressions typed. I tried to implement the state as [PPair] where I define PPair by the GADT:

data PPair where
    PPair :: (String, Expr a) -> PPair

Once this line passed the compiler, I felt that I am doing something really really wrong. I suppressed the thought and went on coding. When I came to writing the code that would extract the value of the variable from the State, I realized the problem:

evalVar k ((PPair (kk, v)):s) = if k == kk then v else evalVar k s

I get:

Inferred type is less polymorphic than expected

which is quite expected. How do I work around this problem? I know I can solve it by breaking up the type over all candidate types a, but is there no neater way?