在使用 Base 的 OCaml 中，如何构造一个包含“int * int”类型元素的集合？

在 F# 中，我只需执行以下操作：

> let x = Set.empty;;
val x : Set<'a> when 'a : comparison

> Set.add (2,3) x;;
val it : Set<int * int> = set [(2, 3)]

我知道在 OCaml 中，当使用 Base 时，我必须提供一个具有比较函数的模块，例如，如果我的元素类型是string

let x = Set.empty (module String);;
val x : (string, String.comparator_witness) Set.t = <abstr>

Set.add x "foo";;
- : (string, String.comparator_witness) Set.t = <abstr>

但我不知道如何构造一个具有类型比较函数的模块int * int。我如何构建/获得这样的模块？

要创建有序数据结构，如 Map、Set 等，您必须提供一个比较器。在 Base 中，比较器是一个一流的模块（打包到值中的模块），它提供比较函数和见证该函数的类型索引。等等，什么？接下来，让我们首先定义一个比较器。如果您已经有一个具有类型的模块

 module type Comparator_parameter = sig 
     type t (* the carrier type *)

     (* the comparison function *)
     val compare : t -> t -> int 

     (* for introspection and debugging, use `sexp_of_opaque` if not needed *)
     val sexp_of_t : t -> Sexp.t
 end

那么你可以只提供给Base.Comparator.Make函子并构建比较器

 module Lexicographical_order = struct 
    include Pair
    include Base.Comparator.Make(Pair)
 end

哪里的Pair模块提供比较功能，

 module Pair = struct
   type t = int * int [@@deriving compare, sexp_of]
 end

现在，我们可以使用比较器来创建有序结构，例如，

 let empty = Set.empty (module Lexicographical_order)

如果您不想为订单创建单独的模块（例如，因为您无法为其提供一个好的名称），那么您可以使用匿名模块，如下所示

 let empty' = Set.empty (module struct
   include Pair
   include Base.Comparator.Make(Pair)
  end)

请注意，Pair模块，传递给Base.Comparator.Make函子必须绑定在全局范围内，否则类型检查器会抱怨。这都是关于这个见证价值的。那么这个见证人是关于什么的，它见证了什么。

任何有序数据结构（例如 Map 或 Set）的语义都取决于顺序函数。比较以不同顺序构建的两个集合是错误的，例如，如果您有两个由相同数字构建的集合，但一个按升序排列，另一个按降序排列，它们将被视为不同的集合。

理想情况下，类型检查器应该防止此类错误。为此，我们需要在集合的类型中对用于构建集合的顺序进行编码。这就是 Base 正在做的事情，让我们看看empty' type,

val empty' : (int * int, Comparator.Make(Pair).comparator_witness) Set.t

and the empty type

val empty : (Lexicographical_order.t, Lexicographical_order.comparator_witness) Set.t

令人惊讶的是，编译器能够看穿名称差异（因为模块具有结构类型）并理解Lexicographical_order.comparator_witness and Comparator.Make(Pair).comparator_witness见证了相同的订单，所以我们甚至可以比较empty and empty',

# Set.equal empty empty';;
- : bool = true

为了巩固您的知识，让我们以相反的顺序构建一组对，

module Reversed_lexicographical_order = struct
  include Pair
  include Base.Comparator.Make(Pair_reveresed_compare)
end

let empty_reveresed =
  Set.empty (module Reversed_lexicographical_order)

(* the same, but with the anonyumous comparator *)
let empty_reveresed' = Set.empty (module struct
    include Pair
    include Base.Comparator.Make(Pair_reveresed_compare)
  end)

和以前一样，我们可以比较反转集的不同变体，

# Set.equal empty_reversed empty_reveresed';;
- : bool = true

但是类型检查器禁止比较不同阶的集合，

# Set.equal empty empty_reveresed;;
Characters 16-31:
  Set.equal empty empty_reveresed;;
                  ^^^^^^^^^^^^^^^
Error: This expression has type
         (Reversed_lexicographical_order.t,
          Reversed_lexicographical_order.comparator_witness) Set.t
       but an expression was expected of type
         (Lexicographical_order.t, Lexicographical_order.comparator_witness) Set.t
       Type
         Reversed_lexicographical_order.comparator_witness =
           Comparator.Make(Pair_reveresed_compare).comparator_witness
       is not compatible with type
         Lexicographical_order.comparator_witness =
           Comparator.Make(Pair).comparator_witness 

这就是比较见证人的用途，它们可以防止非常严重的错误。是的，它比 F# 需要更多的输入，但完全值得，因为它提供了来自类型检查器的更多输入，现在能够检测真正的问题。

最后几点说明。 “比较器”这个词在 Janestreet 图书馆中是一个不断发展的概念，以前它曾经意味着不同的东西。接口也在变化，比如@glennsl提供的例子有点过时了，并且使用Comparable.Make模块而不是新的和更通用的Base.Comparator.Make.

此外，有时编译器在抽象类型时将无法看到比较器之间的相等性，在这种情况下，您需要在 mli 文件中提供共享约束。您可以采取Bitvec_o​​rder https://github.com/BinaryAnalysisPlatform/bap/blob/ad79508e53e28184305fa58d51c6440ce95f47f6/lib/bitvec_order/bitvec_order.mli以图书馆为例。它展示了如何使用比较器来定义相同数据结构的各种顺序以及如何使用共享约束。图书馆文档还解释了各种术语并给出了术语的历史。

最后，如果您想知道如何启用派生预处理器，那么

1. 对于沙丘，添加(preprocess (pps ppx_jane))您的库/可执行规范的节
2. 对于 ocamlbuild 添加-pkg ppx_jane option;
3. 对于顶层（例如，ocaml or utop) use #require "ppx_jane";;（如果 require 不可用，则执行#use "topfind;;"，然后重复）。