Is there a simple and elegant way to add position information to a syntactic tree with mutually recursive types?

Question

Haskell

There is a syntax tree with mutually recursive types LVal and Expr:

data Expr = IntLit Int
          | StrLit String
          | LVal LVal
          | Binop Expr Binop Expr
          | Assign LVal Expr

data Binop = Add | Sub | Mul | Div

data LVal = Var String
          | Dot LVal String
          | Index LVal Expr

It is necessary to add information about the position of expressions in the file to it. There are several options. The first is to add a position to each constructor of each type:

data Expr = IntLit Int Position
          | StrLit String Position
          | LVal LVal Position
          | Binop Expr Binop Expr Position
          | Assign LVal Expr Position

data Binop = Add | Sub | Mul | Div

data LVal = Var String Position
          | Dot LVal String Position
          | Index LVal Expr Position

But working with such trees is no longer as convenient as with ordinary ones. The second option is to represent data types through Fix, but since they are mutually recursive, this approach cannot be implemented. You can of course use Fix2:

newtype Fix2 f g = Fix2 { unFix2 :: f (Fix2 f g) (Fix2 g f) }

But to call the approach with its use a simple language does not turn. The last option is to add a separate positional constructor to each of the types:

data Expr = IntLit Int
          | StrLit String
          | LVal LVal
          | Binop Expr Binop Expr
          | Assign LVal Expr
          | EAnn Expr Position

data Binop = Add | Sub | Mul | Div

data LVal = Var String
          | Dot LVal String
          | Index LVal Expr
          | LAnn LVal Position

Then it is just as convenient to work with types as without positioning information. But in this case, it cannot be guaranteed that each node of the tree is provided with information about the position of the expression.

Question - is there a simple and elegant way to add position information to the syntax tree?

Answer 1

For working with AST, functor encodings are more preferable precisely due to the ability to uniformly slip new features into everyone (and then throw them off at once). And it’s more pleasant to work with ready-made recursion schemes than to open a bicycle factory.
I sketched an example with adding annotations to these expressions: https://repl.it/@ICRainbow/RoundHuskyExabyte
Fix2 is not needed, but you need to clearly understand what the functor and the fixed point will be in which expressions. It's not difficult, but it takes practice.

Answer 2

There seems to be no such way.
And why the second option is inconvenient?
See, for example, haskell-src-exts , where each type has an extra. an element of type l, which may have a position or something else.
In ghc, it is done similarly , but a little differently - some constructors are wrapped in Located