在使用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

the documentation for Map中的一些例子正好显示了这一点。

如果使用他们的PPX，则可以执行以下操作：

Map

否则，完整的实现是：

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

Answer 2

要创建有序的数据结构，例如Map，Set等，您必须提供一个比较器。在Base中，比较器是一流的模块（打包为值的模块），提供比较功能和见证该功能的类型索引。等一下稍后，让我们首先定义一个比较器。如果您已经具有类型

的模块

let int_pair_set = Set.empty (module IntPair)

然后您可以只提供给

 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模块必须绑定在全局范围内，否则，类型检查器将抱怨。这一切都与见证价值有关。因此，这个见证人是关于什么以及它见证了什么。 

[任何有序数据结构的语义，例如Map或Set，取决于顺序函数。比较两个以不同顺序构建的集合是错误的，例如，如果您有两个从相同数字构建的集合，但是一个具有升序，而另一个具有降序，则将它们视为不同的集合。

理想情况下，类型检查器应防止此类错误。为此，我们需要以集合的类型对用于构建集合的顺序进行编码。这就是Base所做的，让我们看一下Base.Comparator.Make类型，

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
这是比较器见证者的目的，它们可以防止非常讨厌的错误。是的，与F＃相比，它需要更多类型的输入，但是完全值得，因为它从类型检查器中提供了更多类型，现在可以检测实际问题。 

几个最后的笔记。 “比较器”一词是Janestreet库中一个不断发展的概念，以前它曾经表示不同的事物。接口也在发生变化，例如@glennsl提供的示例有些过时，并且使用

# 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 

模块而不是新的和更通用的Comparable.Make。

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

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

1. 对于沙丘，将Bitvec_order节添加到您的库/可执行文件中
2. 对于ocamlbuild添加(preprocess (pps ppx_jane))选项；
3. 对于上层水准仪（例如-pkg ppx_jane或ocaml），请使用utop（如果无法满足要求，请执行#require "ppx_jane";;，然后重复）。