为什么我的类型定义在声明为变体时被拒绝为循环,但是否则接受？

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

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