Существует ли простой и элегантный способ добавить информацию о позиции в синтаксическое дерево с взаимно-рекурсивными типами?

Question

[Василий Дёмин]

Есть синтаксическое дерево с взаимно-рекурсивными типами LVal и 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

Необходимо добавить в него информацию о позиции выражений в файле. Есть несколько вариантов. Первый - добавить позицию в каждый конструктор каждого типа:

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

Но работать с такими деревьями уже не так удобно, как с обычными. Второй вариант - представление типов данных через Fix, но, так как они взаимно-рекурсивные, данный подход реализовать не получится. Можно, конечно, использовать Fix2:

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

Но назвать подход с его использованием простым язык не поворачивается. Последним из вариантов является добавление отдельного конструктора с позицией в каждый из типов:

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

Тогда с типами работать получается также удобно, как и без информации о позиционировании. Но в таком случае нельзя гарантировать, что каждый узел дерева снабжён информацией о позиции выражения.

Вопрос - существует ли простой и элегантный способ добавить информацию о позиции в синтаксическое дерево?

Answer 1

[wiz]

Для работы с AST функторные кодировки более предпочтительны как раз за счёт возможности единообразно всем подсовывать новые фичи (а затем разом их скидывать). Да и с готовыми схемами рекурсии приятней работать, чем открывать фабрику велосипедов.

Набросал пример с добавлением аннотаций на эти выражения: https://repl.it/@ICRainbow/RoundHuskyExabyte
Fix2 не нужен, но надо чётко понимать чем будет являться функтор и неподвижная точка в каких выражениях. Это не сложно, но нужна практика.

Comments

[Василий Дёмин]

Именно этот вариант я и хотел использовать, просто у меня не получилось представить LVal и Expr через Fix.

Answer 2

[Александр Ручкин]

Вроде такого способа нет.

А почему второй вариант неудобен?
См, например, haskell-src-exts, там у каждого типа есть доп. элемент типа l, в котором может быть позиция или что-то ещё.
В ghc сделано аналогично, но чуть иначе - некоторые конструкторы обёрнуты в Located

Comments

[Василий Дёмин]

Второй вариант удобен, у думал, что нельзя в моём случае выразить оба типа через Fix

[Александр Ручкин]

Я перепутал, имел в виду первый, с добавлением в каждый конструктор.

[Василий Дёмин]

Александр Ручкин, Он неудобен тем, что приходится в каждой функции разбирать конструктор с дополнительным полем - позицией. Например, у меня есть функция, цель которой проставить выведенные типы в конструкторы. Мне приходится разбирать конструктор, доставать из него позицию и добавлять её в новый конструктор. В сравнении со вторым вариантом он неудобен ещё и тем, что приходится использовать явную рекурсию вместо алгебр типа:
alg :: Functor f => f a -> a