Ocaml自我引用

Question

我创建了类型t =测试int*t ref

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

Answer 1

正如delnan所说,你可以使用循环值:

let rec x = Test (0, ref x)

虽然递归通常用于定义函数,但某些值是可能的.这通常是不可能的,文档中描述了限制.

这个想法是这个值是堆分配的,所以很容易递归地使用它:首先为"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;
 }