Как создать функцию Haskell, которая представит новый тип?

Сейчас я пишу синтаксический анализатор выражений. Я провел лексический и синтаксический анализ, а теперь проверяю типы. У меня есть выражение в такой структуре данных (упрощенная версия):

data Expr = EBinaryOp String Expr Expr
          | EInt Int
          | EFloat Float

А теперь мне нужна функция, которая преобразует это в новый тип, скажем TypedExpr , который также будет содержать информацию о типе. И теперь моя главная проблема в том, как должен выглядеть этот шрифт. У меня есть две идеи - с параметром типа:

data TypedExpr t = TEBinaryOp (TBinaryOp a b t) (TExpr a) (TExpr b)
                 | TEConstant t
addTypes :: (ExprType t) => Expr -> TypedExpr t

или без:

data TypedExpr = TEBinaryOp Type BinaryOp TypedExpr TypedExpr
               | TEConstant Type Dynamic
addTypes :: Expr -> TypedExpr

Я начал с первого варианта, но столкнулся с проблемами, потому что этот подход предполагает, что вы знаете тип выражения до его анализа (для меня это верно в большинстве случаев, но не всегда). Однако мне он нравится, потому что он позволяет мне использовать систему типов Haskell и проверять большинство ошибок во время компиляции.

Можно ли сделать это с помощью первого варианта?

data TypedExpr = TEBinaryOp Type BinaryOp TypedExpr TypedExpr
               | TEConstant Type Dynamic
addTypes :: Expr -> TypedExpr

Я начал с первого варианта, но столкнулся с проблемами, потому что этот подход предполагает, что вы знаете тип выражения до его синтаксического анализа (для меня это верно в большинстве случаев, но не всегда). Однако мне он нравится, потому что он позволяет мне использовать систему типов Haskell и проверять большинство ошибок во время компиляции.

Можно ли сделать это с помощью первого варианта?

data TypedExpr = TEBinaryOp Type BinaryOp TypedExpr TypedExpr
               | TEConstant Type Dynamic
addTypes :: Expr -> TypedExpr

Я начал с первого варианта, но столкнулся с проблемами, потому что этот подход предполагает, что вы знаете тип выражения до его синтаксического анализа (для меня это верно в большинстве случаев, но не всегда). Однако мне это нравится, потому что это позволяет мне использовать систему типов Haskell и проверять большинство ошибок во время компиляции.

Можно ли сделать это с помощью первого варианта?
Какой бы вы выбрали? Почему?
Какие проблемы следует ожидать с каждым вариантом?