OCaml中的递归集

Question

我如何在OCaml中定义一个也可以包含其类型的元素的Set？

为了解释这个问题，我为很多数据类型做了一个类型声明，比如

type value =
  Nil
| Int of int
| Float of float
| Complex of Complex.t
| String of string
| Regexp of regexp
| Char of char
| Bool of bool
| Range of (int*int) list
| Tuple of value array
| Lambda of code
| Set of ValueSet.t (* this isn't allowed in my case since module is declared later*)

此外，我稍后在同一文件中声明了一个用于ValueSet的具体模块：

module ValueSet = Set.Make(struct type t = value let compare = Pervasives.compare end)

问题是ValueSet的elt类型是value，但是value可以是ValueSet，所以我在编译它的时候遇到了麻烦。

所有这些声明都包含在一个名为types.ml的文件中(它有自己的接口types.mli，但没有任何ValueSet模块decl，因为我也不确定它是否可行)。

这个问题能以某种方式解决吗？

Answer 1

您可以使用递归模块。Language manual使用与递归集合类型完全相同的示例来说明此语言功能。下面是相关的摘录。

递归模块定义的一个典型示例是：

模块记录A:签名类型t=字符串的叶节点。t值比较:t -> t -> int end =结构类型t=字符串的叶节点| ASet.t的节点。t让比较t1 t2 = match (t1，t2) with (叶s1，叶节点) -> Pervasives.compare s1 s2 | (Leaf _，-> _) -> 1| (Node _，Leaf _) -> -1 | (Node n1，Node n2) -> ASet.compare n1 n2 end -> ASet : Set.S，类型elt = A.t = Set.Make(A)

它可以指定如下规格：

模块记录A: sig type t=字符串的叶子| ASet的节点。t val比较:T -> t -> int end and ASet: Set.S with type elt = A.t