在存在类型运算符的情况下实现 nested/recursive 数据类型
Implementing nested/recursive datatypes in the presence of type operators
我一直在按照 Pierce 的 类型和编程语言 在 Rust 中实现系统 F-omega，并且我正在寻找有关将递归类型添加到我的指南的指导使用等递归 fold/unfold 运算符实现。我已经添加了 sum、product、record、existential 和 universal 类型。
在系统F（w/o类型运算符）中，我发现它做起来比较简单，我只是让一个访问者在解析后通过AST在案例分析中执行fold/unfold同构或类型构造。
对于 System F omega，由于在类型级别存在 lambda 抽象，情况稍微复杂一些。例如（使用标准 lambda-calc/haskell-ish 语法），假设我想定义一个参数化的 List 数据类型
datatype List a = Cons a (List a) | Nil
这可以在我们的演算中编码为（省略 * 种类）：
type List = μ ΛX::*=>*. ΛA. Cons A (X A) | Nil
substs to: ΛA. Cons A ((μ ΛX::*=>*. ΛA. Cons A (X A) | Nil) A) | Nil
但是一旦我们尝试展开值，这就会出现问题，因为引入了试图再次绑定 A 的新抽象。这似乎可行，只要我们将具体类型 A 存储在某个地方。
或者我们可以'lambda drop'它到：
type ListF = ΛX. ΛA. Cons (A, X) | Nil
type List = ΛA. μ (ListF A)
lambda dropping 非常适合像这样的简单递归类型，并且实现起来也很简单，我可以设想一种自动生成 ListF 类型的方法。但我有一种挥之不去的感觉，觉得这件事有点不对劲。
我一直在尝试阅读有关此的文献（Mendler 风格的迭代、Andreas Abel、Ralph Matthes、Tarmo Uustalu、"Iteration and coiteration schemes for higher-order and nested datatypes" 等），但其中一些有点让我头疼，我不知道如何 实际上 以具体方式实现它。任何建议将不胜感激
List = μ ΛX. ΛA. Cons A (X A) | Nil
-- μF unfolds to F(μF)
= (ΛX. ΛA. Cons A (X A) | Nil) (μ ΛX. ΛA. Cons A (X A) | Nil)
-- substitute *correctly*
= ΛA. Cons A ((μ ΛX. ΛA. Cons A (X A) | Nil) A) | Nil
-- ^ you dropped this!
-- folding back
List = ΛA. Cons A (List A) | Nil
A 除了类型本身之外，不需要在任何地方 "stored"。您在不应该删除包含它的应用程序时删除了它。请注意，您的展开是不友善的。顶级 Cons 的第二个字段具有种类 * => *，但这是不对的。但是原版是好样的，所以展开（应该保留种类）一定是出错了。
"Lambda dropping" 很好，但并不总是可行。考虑
data Binary a = Leaf a | Branch (Binary (a, a))
其中恰好包含 2^n a 一些自然 n。这种类型是不规则递归的，不能像 List 那样用 μ :: (* => *) => * 表示。
type Binary = μ ΛX. ΛA. Leaf A | Branch (X (A, A))
我一直在按照 Pierce 的 类型和编程语言 在 Rust 中实现系统 F-omega，并且我正在寻找有关将递归类型添加到我的指南的指导使用等递归 fold/unfold 运算符实现。我已经添加了 sum、product、record、existential 和 universal 类型。
在系统F（w/o类型运算符）中，我发现它做起来比较简单，我只是让一个访问者在解析后通过AST在案例分析中执行fold/unfold同构或类型构造。
对于 System F omega，由于在类型级别存在 lambda 抽象，情况稍微复杂一些。例如（使用标准 lambda-calc/haskell-ish 语法），假设我想定义一个参数化的 List 数据类型
datatype List a = Cons a (List a) | Nil
这可以在我们的演算中编码为（省略 * 种类）：
type List = μ ΛX::*=>*. ΛA. Cons A (X A) | Nil
substs to: ΛA. Cons A ((μ ΛX::*=>*. ΛA. Cons A (X A) | Nil) A) | Nil
但是一旦我们尝试展开值，这就会出现问题，因为引入了试图再次绑定 A 的新抽象。这似乎可行，只要我们将具体类型 A 存储在某个地方。
或者我们可以'lambda drop'它到：
type ListF = ΛX. ΛA. Cons (A, X) | Nil
type List = ΛA. μ (ListF A)
lambda dropping 非常适合像这样的简单递归类型，并且实现起来也很简单，我可以设想一种自动生成 ListF 类型的方法。但我有一种挥之不去的感觉，觉得这件事有点不对劲。
我一直在尝试阅读有关此的文献（Mendler 风格的迭代、Andreas Abel、Ralph Matthes、Tarmo Uustalu、"Iteration and coiteration schemes for higher-order and nested datatypes" 等），但其中一些有点让我头疼，我不知道如何 实际上 以具体方式实现它。任何建议将不胜感激
List = μ ΛX. ΛA. Cons A (X A) | Nil
-- μF unfolds to F(μF)
= (ΛX. ΛA. Cons A (X A) | Nil) (μ ΛX. ΛA. Cons A (X A) | Nil)
-- substitute *correctly*
= ΛA. Cons A ((μ ΛX. ΛA. Cons A (X A) | Nil) A) | Nil
-- ^ you dropped this!
-- folding back
List = ΛA. Cons A (List A) | Nil
A 除了类型本身之外，不需要在任何地方 "stored"。您在不应该删除包含它的应用程序时删除了它。请注意，您的展开是不友善的。顶级 Cons 的第二个字段具有种类 * => *，但这是不对的。但是原版是好样的，所以展开（应该保留种类）一定是出错了。
"Lambda dropping" 很好，但并不总是可行。考虑
data Binary a = Leaf a | Branch (Binary (a, a))
其中恰好包含 2^n a 一些自然 n。这种类型是不规则递归的，不能像 List 那样用 μ :: (* => *) => * 表示。
type Binary = μ ΛX. ΛA. Leaf A | Branch (X (A, A))