Схемы рекурсии с несколькими типами

Question

Прямо сейчас у меня есть AST для выражения, которое полиморфно по типу рекурсии:

data Expr a = Const Int
            | Add a a

Это было невероятно полезно, позволяя мне использовать тип для простой рекурсии (Fix Expr) и другой, когда мне нужно приложить дополнительную информацию (Cofree Expr ann).

Проблема возникает, когда я хочу ввести другой тип в эту схему рекурсии:

data Stmt a = Compound [a]
            | Print (Expr ?)

Я не уверен, что поставить для термина Expr без введения дополнительных переменных типа и нарушения совместимости со всеми общими функциями, которые я уже написал.

Можно ли это сделать, и если да, то полезный ли это шаблон?

Answer 1

Перспектива рекурсивных схем - рассматривать рекурсивные типы как фиксированные точки функторов. Тип выражений - это фиксированная точка следующего функтора:

data ExprF expr = Const Int
                | Add expr expr

Смысл изменения имени переменной состоит в том, чтобы сделать явным тот факт, что она является заполнителем для фактического типа выражений, который в противном случае был бы определен как:

data Expr = Const Int | Add Expr Expr

В Stmt есть два рекурсивных типа, Expr и Stmt. Таким образом, мы ставим две дыры / неизвестные.

data StmtF expr stmt = Compound [stmt]
                     | Print expr

Когда мы берем фиксированную точку с Fix или Cofree, мы сейчас решаем систему из двух уравнений (одно для Expr, другое для Stmt), и это идет с некоторым количеством шаблонов.

Вместо непосредственного применения Fix или Cofree мы обобщаем, взяв эти комбинаторы с фиксированной точкой (Fix, Cofree, Free) в качестве параметров при построении выражений и операторов:

type Expr_ f = f ExprF
type Stmt_ f = f (StmtF (Expr_ f))

Теперь мы можем сказать Expr_ Fix или Stmt_ Fix для аннотированных деревьев и Expr_ (Flip Cofree ann), Stmt_ (Flip Cofree ann). К сожалению, мы должны заплатить еще один сбор LOC, чтобы типы соответствовали друг другу, и типы становятся еще более запутанными.

newtype Flip cofree a f b = Flip (cofree f a b)

(Это также предполагает, что мы хотим использовать одинаковые Fix или Cofree везде в одно и то же время.)

---

Еще одно представление, которое нужно рассмотреть, это ( в настоящее время называется HKD ):

data Expr f = Const Int
            | Add (f Expr) (f Expr)

data Stmt f = Compount [f Stmt]
            | Print (f (Expr f))

, где вы абстрагируетесь только от аннотации / без аннотации (f = Identity или (,) ann), а не от рекурсии.