recursion - Ocaml 自引用

Question

我创建了 type t = Test of int * t ref

如何创建任何类型为 t 的对象？

Answer 1

正如 delnan 所说，您可以使用循环值:

let rec x = Test (0, ref x)

虽然递归通常用于定义函数，但对于某些值也是可能的。这一般是不可能的，有限制描述 in the documentation .

这个想法是这个值是堆分配的，所以很容易递归使用它:首先为“Test”构造函数分配空间，然后你可以使用“x”分配的构造函数的地址来定义它的字段，甚至如果它指向一个尚未完全定义的值。函数、惰性值、对、记录等都遵循这种模式。当然，规范并没有那么低级(OCaml 手册中没有定义“堆分配”)，有一个限制性稍强的语法规范。

一旦你通过值递归引导了一个值，你就可以构建更精细的值:

let rec x = Test (0, ref x)
let y = Test (1, ref x)
let (Test (_, r)) = x in r := y

你也可以直接这样做

let rec x = Test (0, ref y)
and y = Test (1, ref x)

也可以使用 Obj 产生的“虚拟值”，虽然不推荐。 .这就是 Queue标准库模块实现。

这个定义的一个问题是这些值是循环的。如果您计划迭代此类值的“尾部”，则可能会出现问题。如果您打算使用 int 字段来跟踪结构的“尾长”(0 表示引用是不应遵循的虚拟指针)，这正是 Queue 的方式。模块实现。

还有其他可能的选择。例如，您可以使用一个模型，其中尾指针的可空性通过使用选项类型明确:

type t' = Test of int * t' option ref

let x = Test (0, ref None)
let y = Test (0, ref (Some x))

let rec length (Test (_, tail)) =
  match !tail with
  | None -> 0
  | Some tl -> 1 + length tl 

在这种情况下，您不需要递归来引导您的类型， None足够。当然，由于选项类型具有间接性，因此这会带来适度的性能成本。

PS:请注意，对于诸如此类的单一构造函数类型，使用记录类型可能会更好:

type t = {
  field : int;
  tail : t ref;
 }