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

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) а не от рекурсии.