OCaml 如何接受没有叶案例的递归类型？

Question

众所周知，OCaml 拒绝定义裸递归类型，例如 type t = t -> int 并且 Rosetta Code 中的 Y 组合器示例也不起作用。

然而，最近我发现像 type t = A of (t -> int) 这样的递归类型定义的小调整效果很好。以下代码是一些概念验证工作，用于检查哪一个工作正常。

(* OCaml version 4.08.0 *)
(* Precisely, ocaml-base-compiler.4.08.0 *)

# type t = t -> int;;
Error: The type abbreviation t is cyclic

# type t = int -> t;;
Error: The type abbreviation t is cyclic


# type t1 = A of (int -> t1);;
type t1 = A of (int -> t1)

# let v1 = 
    let rec f _ = A f in
    A f;;
val v1 : t1 = A <fun>


# type t2 = B of (t2 -> int);;
type t2 = B of (t2 -> int)

# let v2 =
    let g _ = 3 in
    B g;;
val v2 : t2 = B <fun>


# type t3 = C of (t3 -> t3);;
type t3 = C of (t3 -> t3)

# let v3 = 
    let rec h _ = C h in
    C h;;
val v3 : t3 = C <fun>

我知道该类型可以递归地定义代数数据类型，如 list 或 tree 类型，但它们都有叶子案例，如 NIL 或 LEAF 构造函数。 t1、t2、t3 都没有叶子案例，但它们没有被拒绝。

我不知道 OCaml 类型系统如何允许这些类型定义。您能解释一下为什么接受 t1、t2、t3 类型以及如何解释值 v1、v2 和 [=25= 的含义吗？ ]？没有叶案例的递归类型有什么实际用途吗？

Answer 1

OCaml 的早期版本很乐意接受 type t = t -> int 等类型。他们甚至推断出他们。这样做的问题是，在大多数实际情况下，这种类型只是掩盖了编程错误。因此，根据大众需求，它们是不允许的，您现在需要一个显式数据类型。如果将 -rectypes 选项与编译器一起使用，您仍然可以获得旧行为。

这只是一个务实的决定。这种类型没有语义问题，至少在像 OCaml 这样的语言中没有。

数据类型不需要像 "leaf" 情况那样具有非递归构造函数，只要至少一个构造函数的类型包含不需要定义类型的另一个值的值。

例如，

type 'a list1 = List1 of 'a * 'a list1 option

是表示非空列表的可能类型。这行得通，因为它包含 List1 (x, None) 作为非递归值。

从这个意义上讲，函数是一个类似的例子。

OCaml 如何接受没有叶案例的递归类型？

How Recursive types with no leaf cases can be accepted in OCaml?

recursion

ocaml

types