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

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

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