如何在不知道元素类型的情况下创建一组元素？
How to create a set of elements without knowing the type of the element?
我 运行 陷入围绕 recursive/mutually 参考模块定义的问题，试图使用 Caml 的 Map/Set 东西。我真的想要那些只适用于类型而不是模块的。我觉得应该可以用 first-class 模块做到这一点，但我没能使语法起作用。
我要的签名是：
module type NonFunctorSet = sig
type 'a t
val create : ('a -> 'a -> int) -> 'a t
val add : 'a t -> 'a -> 'a t
val remove : 'a t -> 'a -> 'a t
val elements : 'a t -> 'a list
end
可能包含其他 Caml.Set 功能。我的想法是这样的：
type 'a t = {
m : (module Caml.Set.S with type elt = 'a);
set : m.t
}
let create (compare : 'a -> 'a -> t) =
module m = Caml.Set.Make(struct type t = 'a let compare = compare end) in
let set = m.empty in
{m = m; set = set;}
end
但由于多种原因，这并不奏效； 'a 没有暴露在正确的位置，我无法在定义 m 的同一记录中引用 m.t，等等
是否有可用的版本？
添加更多关于我的用例的上下文：
我有两个模块，Region 和 Tribe。 Tribe 需要访问 Region 的很多接口，所以我目前正在创建 Tribe 作为函子 MakeTribe(Region : RegionT)。 Region 大部分不需要了解 Tribe，但它确实需要能够存储 Tribe.t 的可变集合，代表居住在该地区的部落。
所以，不知何故，我需要一个RegionT喜欢
module type RegionT = sig
type <region>
val get_local_tribes : <region> -> <tribes>
val add_tribe : <region> -> <tribe> -> unit
...
end
我不太关心<tribe>、<tribes>和<region>这里面的具体语法，只要完整构建的Tribe模块就知道了Region.get_local_tribes 等将产生实际的 Tribe.t
循环依赖问题是在创建模块Tribe之前，类型<tribe>不存在。到目前为止，我的想法是 RegionT.t 实际上是 'a RegionT.t，然后 Tribe 可以简单地引用 Tribe.t Region.t。如果我对在 Region 中保留一个 <tribe> list 感到满意，这一切都很好，但我希望它是一个集合。
根据以下示例代码，我认为这应该是可能的：
module Example : sig
type t
val compare : t -> t -> int
end = struct
type t = int
let compare = Int.compare
end
module ExampleSet = Caml.Set.Make(struct type t = Example.t let compare = Example.compare end)
Example 在其接口中公开的所有内容是一个类型和一个从该类型的两个实例到一个 int 的函数；为什么这比 'a -> 'a -> int 具有相同的东西更重要？
使用基础库中的多态集和映射
在来自 Jane Street 的 Base 和 Core 库中，有序的数据结构，例如映射、集合、哈希表和哈希集，都是作为多态数据结构实现的，而不是像普通 OCaml 标准中那样的函数化版本图书馆。
您可以在 Real World OCaml Maps and Hashtbales 一章中阅读更多关于它们的信息。但这里有快速食谱。当你在函数接口中看到一个比较器时，例如，在 Map.empty 中，它实际上想要你的是给你一个实现比较器接口的 module 。好消息是 Base/Core 中的大多数模块都在实现它，因此您不必担心或对此一无所知即可使用它，例如
# open Base;;
# let empty = Map.empty (module Int);;
val empty : (Base.Int.t, 'a, Base.Int.comparator_witness) Base.Map.t =
<abstr>
# Map.add empty 1 "one";;
- : (Base.Int.t, string, Base.Int.comparator_witness) Base.Map.t
Base.Map.Or_duplicate.t
= `Ok <abstr>
所以简单的规则，如果你想要一个集合、映射、哈希表、哈希集，其中键元素的类型为 foo，只需传递 (module Foo) 作为比较器。
现在，如果您想从您的自定义类型进行映射怎么办？例如，您想按字典顺序比较的一对整数。
首先，我们需要定义sexp_of和比较函数。对于我们的类型。我们将使用 ppx 派生器，但如果需要，手动制作也很容易。
module Pair = struct
type t = int * int [@@deriving compare, sexp_of]
end
现在，要创建一个比较器，我们只需要使用 Base.Comparator.Make 仿函数，例如，
module Lexicographical_order = struct
include Pair
include Base.Comparator.Make(Pair)
end
所以现在我们可以做，
# let empty = Set.empty (module Lexicographical_order);;
val empty :
(Lexicographical_order.t, Lexicographical_order.comparator_witness)
Base.Set.t = <abstr>
# Set.add empty (1,2);;
- : (Lexicographical_order.t, Lexicographical_order.comparator_witness)
Base.Set.t
= <abstr>
尽管 Base 的数据结构是多态的，但它们严格要求提供比较器的模块是实例化的并且是已知的。您可以只使用比较函数来创建多态数据结构，因为 Base 将为每个定义的比较函数实例化一个见证类型，并将其捕获在数据结构类型中以启用二进制方法。无论如何，这是一个复杂的问题，继续阅读以获得更简单（和更难）的解决方案。
在相互依赖的模块上实例化集合
事实上，OCaml 支持相互递归的函子，尽管我建议您通过引入 Region 和 Tribe 所依赖的公共抽象来打破递归，您仍然可以在 OCaml 中编码您的问题，例如，
module rec Tribe : sig
type t
val create : string -> t
val compare : t -> t -> int
val regions : t -> Region.t list
end = struct
type t = string * Region.t list
let create name = name,[]
let compare (x,_) (y,_) = String.compare x y
let regions (_,r) = r
end
and Region : sig
type t
val empty : t
val add_tribe : Tribe.t -> t -> t
val tribes : t -> Tribe.t list
end = struct
module Tribes = Set.Make(Tribe)
type t = Tribes.t
let empty = Tribes.empty
let add_tribe = Tribes.add
let tribes = Tribes.elements
end
打破依赖循环
一个更好的解决方案是重新设计您的模块并打破依赖循环。最简单的方法就是选择一些用于比较部落的标识符，例如，通过他们的唯一名称，
module Region : sig
type 'a t
val empty : 'a t
val add_tribe : string -> 'a -> 'a t -> 'a t
val tribes : 'a t -> 'a list
end = struct
module Tribes = Map.Make(String)
type 'a t = 'a Tribes.t
let empty = Tribes.empty
let add_tribe = Tribes.add
let tribes r = Tribes.bindings r |> List.map snd
end
module Tribe : sig
type t
val create : string -> t
val name : t -> string
val regions : t -> t Region.t list
val conquer : t Region.t -> t -> t Region.t
end = struct
type t = Tribe of string * t Region.t list
let create name = Tribe (name,[])
let name (Tribe (name,_)) = name
let regions (Tribe (_,r)) = r
let conquer region tribe =
Region.add_tribe (name tribe) tribe region
end
还有很多其他选项，一般来说，当你有相互依赖时，它实际上表明你的设计存在问题。所以，我还是会重新审视设计阶段，避免循环依赖。
使用 Vanilla OCaml 标准库创建多态集
这不是一件容易的事，尤其是当您需要处理涉及多个集合的操作时，例如 Set.union。问题是 Set.Make 正在为每个 compare 函数的集合生成一个新类型，所以当我们需要合并两个集合时，我们很难向 OCaml 编译器证明它们是从同一类型。这是可能的，但真的很痛苦，我展示如何做到这一点只是为了阻止你这样做（并展示 OCaml 的动态类型功能）。
首先，我们需要一个 witness 类型，它将集合的 OCaml 类型具体化为具体值。
type _ witness = ..
module type Witness = sig
type t
type _ witness += Id : t witness
end
现在我们可以将我们的多态集合定义为一个包含集合本身和具有操作的模块的存在。它还包含 tid（用于类型标识符），我们稍后将使用它来恢复集合的类型 's。
type 'a set = Set : {
set : 's;
ops : (module Set.S with type elt = 'a and type t = 's);
tid : (module Witness with type t = 's);
} -> 'a set
现在我们可以编写 create 函数，它将接受比较函数并将其变成一个集合，
let create : type a s. (a -> a -> int) -> a set =
fun compare ->
let module S = Set.Make(struct
type t = a
let compare = compare
end) in
let module W = struct
type t = S.t
type _ witness += Id : t witness
end in
Set {
set = S.empty;
ops = (module S);
tid = (module W);
}
这里需要注意的是，每次调用 create 都会生成集合类型 's 的新实例，因此我们可以 compare/union/etc 两个使用相同 create 函数。换句话说，我们实现中的所有集合都应共享同一个祖先。但在此之前，让我们努力实现至少两个操作，add 和 union，
let add : type a. a -> a set -> a set =
fun elt (Set {set; tid; ops=(module Set)}) -> Set {
set = Set.add elt set;
ops = (module Set);
tid;
}
let union : type a. a set -> a set -> a set =
fun (Set {set=s1; tid=(module W1); ops=(module Set)})
(Set {set=s2; tid=(module W2)}) ->
match W1.Id with
| W2.Id -> Set {
set = Set.union s1 s2;
tid = (module W1);
ops = (module Set);
}
| _ -> failwith "sets are potentially using different types"
现在，我们可以玩一下了，
# let empty = create compare;;
val empty : '_weak1 set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x1 = add 1 empty;;
val x1 : int set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x2 = add 2 empty;;
val x2 : int set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x3 = union x1 x2;;
val x3 : int set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x4 = create compare;;
val x4 : '_weak2 set = Set {set = <poly>; ops = <module>; tid = <module>}
# union x3 x4;;
Exception: Failure "sets are potentially using different types".
#
我 运行 陷入围绕 recursive/mutually 参考模块定义的问题，试图使用 Caml 的 Map/Set 东西。我真的想要那些只适用于类型而不是模块的。我觉得应该可以用 first-class 模块做到这一点，但我没能使语法起作用。
我要的签名是：
module type NonFunctorSet = sig
type 'a t
val create : ('a -> 'a -> int) -> 'a t
val add : 'a t -> 'a -> 'a t
val remove : 'a t -> 'a -> 'a t
val elements : 'a t -> 'a list
end
可能包含其他 Caml.Set 功能。我的想法是这样的：
type 'a t = {
m : (module Caml.Set.S with type elt = 'a);
set : m.t
}
let create (compare : 'a -> 'a -> t) =
module m = Caml.Set.Make(struct type t = 'a let compare = compare end) in
let set = m.empty in
{m = m; set = set;}
end
但由于多种原因，这并不奏效； 'a 没有暴露在正确的位置，我无法在定义 m 的同一记录中引用 m.t，等等
是否有可用的版本？
添加更多关于我的用例的上下文：
我有两个模块，Region 和 Tribe。 Tribe 需要访问 Region 的很多接口，所以我目前正在创建 Tribe 作为函子 MakeTribe(Region : RegionT)。 Region 大部分不需要了解 Tribe，但它确实需要能够存储 Tribe.t 的可变集合，代表居住在该地区的部落。
所以，不知何故，我需要一个RegionT喜欢
module type RegionT = sig
type <region>
val get_local_tribes : <region> -> <tribes>
val add_tribe : <region> -> <tribe> -> unit
...
end
我不太关心<tribe>、<tribes>和<region>这里面的具体语法，只要完整构建的Tribe模块就知道了Region.get_local_tribes 等将产生实际的 Tribe.t
循环依赖问题是在创建模块Tribe之前，类型<tribe>不存在。到目前为止，我的想法是 RegionT.t 实际上是 'a RegionT.t，然后 Tribe 可以简单地引用 Tribe.t Region.t。如果我对在 Region 中保留一个 <tribe> list 感到满意，这一切都很好，但我希望它是一个集合。
根据以下示例代码，我认为这应该是可能的：
module Example : sig
type t
val compare : t -> t -> int
end = struct
type t = int
let compare = Int.compare
end
module ExampleSet = Caml.Set.Make(struct type t = Example.t let compare = Example.compare end)
Example 在其接口中公开的所有内容是一个类型和一个从该类型的两个实例到一个 int 的函数；为什么这比 'a -> 'a -> int 具有相同的东西更重要？
使用基础库中的多态集和映射
在来自 Jane Street 的 Base 和 Core 库中，有序的数据结构，例如映射、集合、哈希表和哈希集，都是作为多态数据结构实现的，而不是像普通 OCaml 标准中那样的函数化版本图书馆。
您可以在 Real World OCaml Maps and Hashtbales 一章中阅读更多关于它们的信息。但这里有快速食谱。当你在函数接口中看到一个比较器时，例如，在 Map.empty 中，它实际上想要你的是给你一个实现比较器接口的 module 。好消息是 Base/Core 中的大多数模块都在实现它，因此您不必担心或对此一无所知即可使用它，例如
# open Base;;
# let empty = Map.empty (module Int);;
val empty : (Base.Int.t, 'a, Base.Int.comparator_witness) Base.Map.t =
<abstr>
# Map.add empty 1 "one";;
- : (Base.Int.t, string, Base.Int.comparator_witness) Base.Map.t
Base.Map.Or_duplicate.t
= `Ok <abstr>
所以简单的规则，如果你想要一个集合、映射、哈希表、哈希集，其中键元素的类型为 foo，只需传递 (module Foo) 作为比较器。
现在，如果您想从您的自定义类型进行映射怎么办？例如，您想按字典顺序比较的一对整数。
首先，我们需要定义sexp_of和比较函数。对于我们的类型。我们将使用 ppx 派生器，但如果需要，手动制作也很容易。
module Pair = struct
type t = int * int [@@deriving compare, sexp_of]
end
现在，要创建一个比较器，我们只需要使用 Base.Comparator.Make 仿函数，例如，
module Lexicographical_order = struct
include Pair
include Base.Comparator.Make(Pair)
end
所以现在我们可以做，
# let empty = Set.empty (module Lexicographical_order);;
val empty :
(Lexicographical_order.t, Lexicographical_order.comparator_witness)
Base.Set.t = <abstr>
# Set.add empty (1,2);;
- : (Lexicographical_order.t, Lexicographical_order.comparator_witness)
Base.Set.t
= <abstr>
尽管 Base 的数据结构是多态的，但它们严格要求提供比较器的模块是实例化的并且是已知的。您可以只使用比较函数来创建多态数据结构，因为 Base 将为每个定义的比较函数实例化一个见证类型，并将其捕获在数据结构类型中以启用二进制方法。无论如何，这是一个复杂的问题，继续阅读以获得更简单（和更难）的解决方案。
在相互依赖的模块上实例化集合
事实上，OCaml 支持相互递归的函子，尽管我建议您通过引入 Region 和 Tribe 所依赖的公共抽象来打破递归，您仍然可以在 OCaml 中编码您的问题，例如，
module rec Tribe : sig
type t
val create : string -> t
val compare : t -> t -> int
val regions : t -> Region.t list
end = struct
type t = string * Region.t list
let create name = name,[]
let compare (x,_) (y,_) = String.compare x y
let regions (_,r) = r
end
and Region : sig
type t
val empty : t
val add_tribe : Tribe.t -> t -> t
val tribes : t -> Tribe.t list
end = struct
module Tribes = Set.Make(Tribe)
type t = Tribes.t
let empty = Tribes.empty
let add_tribe = Tribes.add
let tribes = Tribes.elements
end
打破依赖循环
一个更好的解决方案是重新设计您的模块并打破依赖循环。最简单的方法就是选择一些用于比较部落的标识符，例如，通过他们的唯一名称，
module Region : sig
type 'a t
val empty : 'a t
val add_tribe : string -> 'a -> 'a t -> 'a t
val tribes : 'a t -> 'a list
end = struct
module Tribes = Map.Make(String)
type 'a t = 'a Tribes.t
let empty = Tribes.empty
let add_tribe = Tribes.add
let tribes r = Tribes.bindings r |> List.map snd
end
module Tribe : sig
type t
val create : string -> t
val name : t -> string
val regions : t -> t Region.t list
val conquer : t Region.t -> t -> t Region.t
end = struct
type t = Tribe of string * t Region.t list
let create name = Tribe (name,[])
let name (Tribe (name,_)) = name
let regions (Tribe (_,r)) = r
let conquer region tribe =
Region.add_tribe (name tribe) tribe region
end
还有很多其他选项，一般来说，当你有相互依赖时，它实际上表明你的设计存在问题。所以，我还是会重新审视设计阶段，避免循环依赖。
使用 Vanilla OCaml 标准库创建多态集
这不是一件容易的事，尤其是当您需要处理涉及多个集合的操作时，例如 Set.union。问题是 Set.Make 正在为每个 compare 函数的集合生成一个新类型，所以当我们需要合并两个集合时，我们很难向 OCaml 编译器证明它们是从同一类型。这是可能的，但真的很痛苦，我展示如何做到这一点只是为了阻止你这样做（并展示 OCaml 的动态类型功能）。
首先，我们需要一个 witness 类型，它将集合的 OCaml 类型具体化为具体值。
type _ witness = ..
module type Witness = sig
type t
type _ witness += Id : t witness
end
现在我们可以将我们的多态集合定义为一个包含集合本身和具有操作的模块的存在。它还包含 tid（用于类型标识符），我们稍后将使用它来恢复集合的类型 's。
type 'a set = Set : {
set : 's;
ops : (module Set.S with type elt = 'a and type t = 's);
tid : (module Witness with type t = 's);
} -> 'a set
现在我们可以编写 create 函数，它将接受比较函数并将其变成一个集合，
let create : type a s. (a -> a -> int) -> a set =
fun compare ->
let module S = Set.Make(struct
type t = a
let compare = compare
end) in
let module W = struct
type t = S.t
type _ witness += Id : t witness
end in
Set {
set = S.empty;
ops = (module S);
tid = (module W);
}
这里需要注意的是，每次调用 create 都会生成集合类型 's 的新实例，因此我们可以 compare/union/etc 两个使用相同 create 函数。换句话说，我们实现中的所有集合都应共享同一个祖先。但在此之前，让我们努力实现至少两个操作，add 和 union，
let add : type a. a -> a set -> a set =
fun elt (Set {set; tid; ops=(module Set)}) -> Set {
set = Set.add elt set;
ops = (module Set);
tid;
}
let union : type a. a set -> a set -> a set =
fun (Set {set=s1; tid=(module W1); ops=(module Set)})
(Set {set=s2; tid=(module W2)}) ->
match W1.Id with
| W2.Id -> Set {
set = Set.union s1 s2;
tid = (module W1);
ops = (module Set);
}
| _ -> failwith "sets are potentially using different types"
现在，我们可以玩一下了，
# let empty = create compare;;
val empty : '_weak1 set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x1 = add 1 empty;;
val x1 : int set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x2 = add 2 empty;;
val x2 : int set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x3 = union x1 x2;;
val x3 : int set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x4 = create compare;;
val x4 : '_weak2 set = Set {set = <poly>; ops = <module>; tid = <module>}
# union x3 x4;;
Exception: Failure "sets are potentially using different types".
#