module - 如何在 OCaml 中使用集合？

Question

我想写一个函数，给定一个非负整数 n，返回 {1,...,n} 的幂集。所以我想使用找到的 Set.S 模块 here .但我似乎无法导入它。当我运行以下代码时:

open Set.S

let rec power_set n =
  if n = 0 then add empty empty else union (iter (add n s) power_set (n-1)) (power_set (n-1));;

let print_set s = SS.iter print_endline s;;

print_set (power_set 2)

我得到错误:

File "countTopologies.ml", line 1, characters 5-10:
Error: Unbound module Set.S

也许我只是没有在我的计算机上安装 Set.S 模块？ (我只完成了安装 OCaml 所需的基本工作)。如果是这种情况，我将如何获得它？

Answer 1

Set.S是模块类型，而不是模块。您只能打开模块。实际上，模块Set包含三个要素:

模块类型OrderedType表示实现有序类型的模块的类型；

模块类型S表示实现 Set 的模块类型数据结构;

仿函数 Make采用 OrderedType 类型的模块并返回 S 类型的模块.

要获得一组模块，您需要使用 Set.Make 创建它仿函数。仿函数有一个参数——集合元素的模块。在现代 OCaml (4.08+) 中，您可以为整数创建一个集合模块，如下所示:

module Ints = Set.Make(Int)

然后你可以像这样使用，
让数字 = Ints.of_list [1;2;3]
断言(Ints.mem 2 个数字)
对于不提供 Int 的旧版 OCaml模块，或者对于非标准(自定义)类型，您需要定义自己的模块来实现 OrderedType接口(interface)，例如，

 module Int = struct 
   type t = int 
   (* use Pervasives compare *)
   let compare = compare
 end

 module Ints = Set.Make(Int)

您还可以使用非标准库，例如 Janestreet 的 Core 库，它提供了开箱即用的集合。核心库有一个 Int已经负责集合、映射、哈希表的模块，因此可以在没有任何仿函数的情况下访问它:

open Core.Std

let nil = Int.Set.empty

或者，在 Janestreet Core 或 Base 库的现代(2018-2019)版本中，您可以使用多态集合/映射，这要求您仅在创建新集合或映射时为键指定模块，例如，像这样

open Base (* or Core, or Core_kernel *)

let nil = Set.empty (module Int)
let one = Set.add nil 1
let two = Set.singleton (module Int) 2