Ocaml中的记录中的容器

Question

我想到的数据结构涉及一个存储唯一字符串的成员的记录。 抽象地，这是我心目中的记录：

struct A { 
name: string; 
neighbors: Set of String; 
}; 

但我似乎无法创建OCaml中记录库内所设定的容器。鉴于Set是一个函数而不是传统类型，我不知道这是如何完成的。

Answer 1

Set是一个仿函数，它为每种你想要的类型实例化一个新类型;因为它需要知道比较函数，所以你不能像那样做string list（除非你使用PSet，多态集合，从Batteries Included或extlib）。所以：

module StringSet = Set.Make(String);; (* or use BatSet.StringSet *) 
type record = { 
    name: string; 
    neighbors: StringSet.t; 
}; 

带电池多态集（注意它，因为它不键入检查您使用相同的比较功能）：

type record = { 
    name: string; 
    neighbors: string BatSet.t 
}; 

Answer 2

您需要了解例如，“字符串列表”与您要构建的“字符串集合”之间的区别。

对于列表，该类型是'一个列表，因为您需要对构建列表的列表内容一无所知。对于一个集合，您需要记录（N）时间访问权限，为此，您需要根据元素的顺序来组织集合。所以，你需要能够比较它们。 OCaml提供了一个默认的比较函数（Pervasives.compare），但是该函数并不总是最好的：它使用起来很昂贵（例如整数），并且它一直不工作（它使用的是字典顺序值的结构，这并不总是你想要的顺序）。在OCaml中，当一个类型依赖于一个值，这就是“set”的情况，但也是“排序列表”的情况，你需要使用一个仿函数来定义类型，并且应用函数来获得新类型。

这就是这段代码为你做：

模块StringSet = Set.Make（字符串）

等同于：

module StringSet = Set.Make(struct 
    type t = string 
    let compare = compare 
end) 

其中“让比较=比较“表示比较函数是默认值（第二个比较是指Pervasives.compare）。您可以直接使用“字符串”，因为字符串模块已经包含“type t = string”和“let compare = compare”。