在使用 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类型比较函数的模块。我如何construct/obtain这样的模块？

Answer 1

the documentation for 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)

Answer 2

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

的模块

 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)

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

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

理想情况下，类型检查器应该可以防止此类错误。为此，我们需要在集合的类型中对用于构建集合的顺序进行编码。这就是 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# 需要更多的输入，但完全值得，因为它从类型检查器中提供了更多的输入，现在能够检测到真正的问题。

一些最后的笔记。 "comparator" 这个词在 Janestreet 图书馆中是一个不断发展的概念，以前它曾经有不同的含义。接口也在变化，比如@glennsl 提供的示例有点过时，并使用 Comparable.Make 模块而不是新的更通用的 Base.Comparator.Make 模块。

此外，有时编译器在抽象类型时无法看到比较器之间的相等性，在这种情况下，您需要在 mli 文件中提供共享约束。您可以以 Bitvec_order 库为例。它展示了如何使用比较器来定义相同数据结构的各种顺序以及如何使用共享约束。库文档还解释了各种术语并提供了术语的历史。

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

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

Answer 3

对于我来说，可以使用Core库的Poly子模块：

Set.Poly.empty

但是，与明确指定 Set 的类型相比，我不太确定使用 Poly 的 advantages/disadvantages 是什么。

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

In OCaml using Base, how do you construct a set with elements of type `int * int`?

ocaml

module

functor