3

我在使用 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

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

4

2 回答 2

8

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

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

于 2015-10-03T20:41:01.727 回答
1

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

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

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

甚至更好

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

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

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

 type t = Constr x

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

于 2015-10-04T14:31:48.283 回答