是否有 concise/inline 方法可以在不显式命名其类型的情况下创建 Set 值？

Question

在大多数具有参数/泛型类型的语言中，您可以编写一个（类型）表达式来表示 'Set of something'。例如。 Set<Integer> 在 Java.

类似地，在 OCaml 中，我们对列表有类似的东西 int list。

不过，在OCaml中好像没有办法说int set。（或者也许我只是还没有找到/弄清楚如何）。

没有'generic Set'类型。相反，有一个 Set 模块，其中包含一个名为 Make 的 'functor'，您将其传入另一个包含 'ordered' 类型定义的模块。

所以我们必须做类似的事情：

module IntSet = Set.Make(Int)
let numbers : IntSet.empty

因此我们声明了一个模块 IntSet，其中包含对 int 的集合进行操作的函数。它还包含一个 IntSet.t 类型，本质上等同于 Java.

中的 Set<Int>

这在某种程度上是有道理的。但有点烦人的是，这迫使我们为我们想要在程序中使用的每种类型的 Set 选择显式名称，并在某个地方显式定义它（IntSet、StringSet、FloatSet，...）。

有没有办法避免这种情况？也许一些内联/匿名/简洁的方式类似于 Java Set<...> 在本地构建 IntSet 模块而不给它一个名字？

我试过类似的方法，但它不起作用。

let numbers = Set.Make(Int).empty
(*            ^^^^^^^^ unbound constructor Set.Make *)

奇怪的是，这种符号似乎在 .mli 文件中起作用，声明仅限类型：

val numbers : Set.Make(Int).t

这给了一些希望，它应该是可能的。

Answer 1

总的来说，我认为这是您可能需要习惯的事情。符号比其他一些语言重一点，但 OCaml 模块也比其他语言的模块更具表现力。

也就是说，您可以避免使用 let open:

为模块命名

# let numbers = let open Set.Make(Int) in empty;;
val numbers : Set.Make(Int).t = <abstr>
# let morenumbers = let open Set.Make(Int) in add 14 numbers;;
val morenumbers : Set.Make(Int).t = <abstr>

至少，这对我有用。

实质是您需要在语法中使用一个可以放置模块名称的位置。在表达式语法中 Set.Make(Int).t 看起来像一个值构造函数。（或者无论如何，这就是我解释行为的方式。）

更新

作为一个比我所指出的聪明得多的评论者，最好记住这不是 OCaml 中的好风格。正如我所说，从大局来看，您可能只是想习惯给模块命名。

Answer 2

重要的一点是，不可能只从一个类型构建一个集合（具有 ln(n) 查询复杂性）。集合由 类型和 类型的比较函数定义。例如，Java 的 TreeSet<T> 仅对实现比较器接口的类型 T 有效，或者如果构造函数被赋予比较器函数。

OCaml 的基于函子的集合使这种关系在类型级别变得明显可见。例如，我可以将 float 的集合和温度定义为浮点数（温度之间的物理正确比较）

module Float_set = Set.Make(Float)
module Temperature = struct
  type t = float
  let compare x y = match x > 0, y > 0 with
  | true, false -> -1 (* negative temperatures are hotter than positive ones *) 
  | false, true -> 1
  | false, false -> Stdlib.compare x y
  | true, true -> Stdlib.compare y x
end
module Temperature_set = Set.Make(Temperature)

并且类型 Temperature_set.t 和 Float_set.t 将是不同的和不兼容的，即使两个集合的元素都是浮点数。

Answer 3

如果您可以使用 Jane Street 的替换 Base 库而不是标准库，它有一个 Set module 本质上包含一个比较作为类型的一部分；它可以将模块作为函数的参数来创建一个新的集合，您可以使用它来代替仿函数：

$ ocaml
# #require "base";;
# open Base;;
# let foo = Set.empty (module Int);;
val foo : (Base.Int.t, Base.Int.comparator_witness) Base.Set.t = <abstr>
# let foo2 = Set.add foo 5;;
val foo2 : (Base.Int.t, Base.Int.comparator_witness) Base.Set.t = <abstr>
# Set.to_list foo2;;
- : Base.Int.t list = [5]

Real World Ocaml 详细解释了它如何与 comparator_witness 类型一起使用以及如何制作您自己的模块以进行自定义比较。

Answer 4

关于是否可以避免显式命名由 Set.Make 仿函数返回的模块的问题，您已收到答案：不是真的。

但是，值得一提的是，为什么您一开始就使用 Set 模块处于这个位置，这是因为在模块签名中对应用于值类型的类型变量进行了通用量化。这样的类型变量不再意味着“编译器推断出的某种类型”；他们代表“所有类型”。在关联的实现模块中，必须实现具有多态签名的函数或其他值，以便相关类型变量能够是任何类型。

采用如下签名的集合模块，其中 'add' 函数调用一些内部比较函数以确定元素的顺序：

  sig
    type 'a t

    ...

    val empty : 'a t
    val add : 'a t -> 'a -> 'a t
  end

这样的签名是有问题的，因为要在这个签名下编译 add 函数，它必须是多态的，这反过来意味着它应用的内部比较函数也必须是 'a -> ' 类型的多态一个 -> 整数。标准库确实以 Stdlib.compare 多态结构比较函数的形式提供了这样的功能，但有一些 well-known 缺点：即结构比较对于复杂数据结构不可靠，在实践中不能用于比较所有的东西——例如，如果你尝试将 Stdlib.compare 应用于一个函数，你将得到一个异常。因此，比较函数通常最好是单态的——也就是说，您通常希望对整数、浮点数、字符串等或您自己设计的实体进行不同的实现。

实现这一目标的一种方法，即标准库使用的方法，是在一开始就使元素类型成为单态的，因此：

  sig
    type t
    type elt

    ...

    val empty : t
    val add : t -> elt -> t
  end

现在内部比较函数也可以是单态的，类型elt -> elt -> int。使用应用于提供元素类型和比较功能的结构的函子最容易构造这样的模块。仿函数的输出模块的类型然后带有共享约束，例如 'Set.S with type elt = [element type]'：有关更多信息，请参阅标准库的 Set.Make 仿函数。

上述通用量化规则的一个例外（ocaml 类型系统的紧急属性）涉及高阶函数，特别是将另一个函数作为参数的函数。即使参数化，这样的参数也可以传递给单态函数（在集合的情况下提供，它与构造集合的元素类型相匹配）。所以 'empty' 可以变成一个函数，可能会重命名它 'make' 结果，它将比较函数作为参数并将比较函数存储在记录或元组中以供将来与根一起使用集合的节点，导致签名如下所示：

  sig
    type 'a t
    type comp = 'a -> 'a -> int

    ...

    val make : comp -> 'a t
    val add : 'a t -> 'a -> 'a t
  end

然而，这会遇到一个问题，即一个函数需要多个集合作为参数，比如为了连接两个集合。为了正确工作，可能有必要为相同的比较函数构建两个集合。这需要使用第二个类型参数对集合进行参数化，该参数包含表示比较函数的任意幻像类型，这有点乏味。这就是 Jane Street 图书馆 Base.Set 模块的本质。

在 C++ 或 Java 等语言中，您可以使用泛型为 sub-set 类型实现容器，例如，为它们实现 Comparable 接口或概念。您不能在 ocaml 的类型系统下使用类型变量直接执行此操作。仿函数恰好是实现类似功能的更直接的方法之一，但它确实具有您所提到的有点冗长的语法。

是否有 concise/inline 方法可以在不显式命名其类型的情况下创建 Set 值？

Is there a concise/inline way to create Set values without explicitly naming their type?

ocaml

module

signature

functor