types - 为什么我的类型定义在声明为变体时被拒绝为循环，但在其他情况下被接受？

Question

我在使用 OCaml 实现 Chris Okasaki 的 Purely Functional Data Structures 中的一些数据结构时乱七八糟，遇到了这种类型定义:

 type tree = Node of int * int * tree list;;

我认为它不需要标签，因为它不是联合类型，所以我尝试消除标签，但出现以下错误:

# type tree = int * int * tree list;;
Characters 5-33:
type tree = int * int * tree list;;
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: The type abbreviation tree is cyclic

为什么两个看似等效的类型定义会发生这种情况？

Answer 1

在类似 ML 的语言中，递归类型的定义是递归不通过变体类型的定义。这是一个实用的定义，从某种意义上说，它往往会导致更有用的类型检查。

递归类型没有什么棘手的。您可以使用 -rectypes 标志在 OCaml 中启用对递归类型的支持。

$ ocaml -rectypes
        OCaml version 4.02.1

# type tree = int * int * tree list;;
type tree = int * int * tree list
# let x: tree = (3, 3, [(4, 4, [])]);;
val x : tree = (3, 3, [(4, 4, [])])

启用递归类型时，所有常见的强类型保证都会出现。主要的缺点是接受了许多非预期的程序。换句话说，递归类型的存在通常表明存在编程错误。