2

我在尝试使用 Caml 的 Map/Set 东西时遇到了递归/相互引用模块定义的问题。我真的想要只适用于类型而不是模块的那些。我觉得应该可以使用一流的模块来做到这一点，但是我无法使语法正常工作。

我想要的签名是：

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 的同一记录中引用 mt 等。

有这样的版本吗？

添加有关我的用例的更多上下文：

我有两个模块，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。如果我对保留一个<tribe> listinside感到满意，这一切都很好Region，但我希望它是一个集合。

根据以下示例代码，我觉得这应该是可能的：

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具有相同事物的 更重要？

4

1 回答 1

3

使用基础库中的多态集合和映射

在来自 Jane Street 的 Base 和 Core 库中，有序数据结构，例如映射、集合、哈希表和哈希集，都实现为多态数据结构，而不是像原始 OCaml 标准库中的函数化版本。

您可以在 Real World OCaml Maps and Hashtbales一章中了解更多信息。但这里有快速食谱。当您在函数接口中看到比较器时，例如，Map.empty它实际上想要您给您一个实现比较器接口的模块。好消息是 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>

所以简单的规则，如果你想要一个 set,map,hashtable,hashset ，其中 key 元素具有 type ，只需作为比较器foo传递。(module Foo)

现在，如果您想从自定义类型进行映射怎么办？例如，您想按字典顺序比较的一对整数。

首先，我们需要定义 sexp_of 和 compare 函数。对于我们的类型。我们将为此使用 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 的动态类型功能）。

首先，我们需要一个见证类型，它将集合的 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创建的两个集合。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".
#
于 2021-05-12T19:22:53.953 回答