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

Question

在 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。我如何构建/获得这样的模块？

Answer 1

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

 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）的语义都取决于 order 函数。比较以不同顺序构建的两个集合是错误的，例如，如果您有两个由相同数字构建的集合，但是一个是升序，另一个是降序，它们将被视为不同的集合。

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

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

和empty类型

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

令人惊讶的是，编译器能够看透名称差异（因为模块具有结构化类型）并理解它们Lexicographical_order.comparator_witness并Comparator.Make(Pair).comparator_witness看到相同的顺序，因此我们甚至可以比较empty和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库为例。它展示了如何使用比较器来定义相同数据结构的各种顺序以及如何使用共享约束。图书馆文档还解释了各种术语并提供了术语的历史。

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

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

Answer 2

文档Map中有一些示例可以准确地说明这一点。

如果您使用他们的 PPX，您可以这样做：

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

  include T
  include Comparable.Make(T)
end

否则完整的实现是：

module IntPair = struct
  module T = struct
    type t = int * int
    let compare x y = Tuple2.compare Int.compare Int.compare
    let sexp_of_t = Tuple2.sexp_of_t Int.sexp_of_t Int.sexp_of_t
  end

  include T
  include Comparable.Make(T)
end

然后您可以使用此模块创建一个空集：

let int_pair_set = Set.empty (module IntPair)