haskell - 为什么在 Haskell 中类型同义词不允许递归？

Question

任何人都可以解释为什么这些都可以愉快地编译:

data A a b = A { a :: a, b :: b }
newtype B a = B (A a (B a))
newtype C = C (A Int C)

但是我不能通过类型同义词创建类似的递归定义类型？

type B a = A a (B a)
type C = A Int C

虽然很明显data B a = A { a :: a, b :: B a }工作得很好。

有什么方法可以避免在我希望类型递归的任何地方处理那个额外的构造函数 X ？我主要是传递选择 b 的访问器函数。无论如何，所以我基本上没问题，但是如果存在简单的规避机制，我想知道它。

我应该使用任何编译指示来提高专用数据类型 C 的性能？只是专门的东西？

在 A a b 之间复制的任何巧妙技巧和 A c d仅定义 a -> b和 c -> d映射而不复制记录两次？恐怕A的领域将在 future 发生变化。也许是 Haskell 模板？

Answer 1

这与 Equi-recursive types 有关与 iso-recursive types 相比. Haskell 使用 iso-recursive 类型实现递归类型，这需要程序员在类型递归发生时告诉类型检查器。您标记它的方式是使用特定的构造函数，简单的类型同义词不允许您拥有。

等递归类型允许编译器推断递归发生的位置，但它会导致更复杂的类型检查器，并且在某些看似简单的情况下，问题是无法确定的。

如果您想很好地讨论 equi 与 iso 递归类型，请查看 Benjamin Pierce 的优秀 Types and Programming Languages

简短的回答:因为类型同义词不引入构造函数，并且 haskell 需要构造函数在类型级别显式标记递归，所以不能使用递归类型同义词。