OCaml：集合模块

Question

我想使用OCaml生成数据集并对其进行比较。我看过了模块类型的文档，例如 Set.OrderType ， Set.Make 等，但是我无法弄清如何初始化集合或以其他方式使用它们。

- Nick Heiner

Answer 1

使用函子接口定义集合。对于任何给定的类型，您必须使用Set.Make函子为该类型创建一个Set模块。标准库的不幸疏忽是它们没有为内置类型定义Set实例。在大多数简单情况下，使用Pervasives.compare就足够了。这是适用于int的定义：

module IntSet = Set.Make( 
  struct
    let compare = Pervasives.compare
    type t = int
  end )

模块IntSet将实现Set.S接口。现在，您可以使用IntSet模块操作集合：

let s = IntSet.empty ;;
let t = IntSet.add 1 s ;;
let u = IntSet.add 2 s ;;
let tu = IntSet.union t u ;;

请注意，您不必显式地将输入结构定义为OrderedType，类型推断会为您完成这项工作。或者，您可以使用以下定义：

module IntOrder : Set.OrderedType = struct
  type t = int
  let compare = Pervasives.compare
end

module IntSet = Set.Make( IntOrder )

这样做的好处是您可以重复使用同一模块来实例化一个Map：

module IntMap = Map.Make( IntOrder )

使用函数对象会失去一些泛型性，因为元素的类型是固定的。例如，您将无法定义一个函数，它接受某种任意类型的Set并对其执行某些操作。(幸运的是，Set模块本身声明了许多有用的操作Set)。

- Chris Conway

---

你将无法定义一个接受任意类型Set的函数。但是，您可以通过在接受特定Set模块作为参数的functor内定义该函数来实现相同的功能。但是，为了使用它，程序员必须创建另一个具有此functor的模块，因此不太方便。 - newacct

没错，这就是一直使用函数对象的乐趣。 - Chris Conway

Answer 2

除了Chris的回答之外，还值得一提的是，一些标准库模块已经遵循了OrderedType接口规范。例如，你只需要：

module StringSet = Set.Make(String) ;;       (* sets of strings *)
module Int64Set = Set.Make(Int64) ;;         (* sets of int64s *)
module StringSetSet = Set.Make(StringSet) ;; (* sets of sets of strings *)

以下是StringSet的简单使用示例; 请记住，集合是函数式数据结构，因此向集合添加新元素将返回一个新的集合：

let set = List.fold_right StringSet.add ["foo";"bar";"baz"] StringSet.empty ;;
StringSet.mem "bar" set ;; (* returns true *)
StringSet.mem "zzz" set ;; (* returns false *)

- Bruno De Fraine