> writing separate genEvalNat and genEvalString functions

.. here is another possibility:

data GenExpr_nat a = ...
data GenExpr_string a = ...


class GenEval exp a where
genEval ::exp a -> a

instance GenEval GenExpr_nat a where
...

instance GenEval GenExpr_string a where
...
​