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

Question

我在使用 OCaml 实现 Chris Okasaki 的纯函数式数据结构中的一些数据结构时遇到了这个类型定义：

 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, [])])

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

Answer 2

第一个类型定义定义了新类型。当您省略构造函数名称时，您实际上不是在定义新类型，而是在引入类型缩写。默认情况下，类型缩写不允许递归，因为通常这不是你的意思。

您可以使用任何定义新类型的类型定义语法来创建递归类型，而不仅仅是变体。记录也可以，例如

type tree = { node : int * int * tree list }

甚至更好

type tree = {
  value : int;
  depth : int;
  children : tree list;
}

（注意：字段名称是任意选择的，因为我不知道它们的原始用途）

总而言之，求和类型不仅用于引入不相交的类型集，还用于创建新类型，因此：

 type t = Constr x

引入类型 t，可以使用构造函数 Constr 从类型 x.

的值构造

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

Why is my type definition rejected as cyclic when declared as a variant, but accepted otherwise?

ocaml

types

functional-programming

ml

cyclic