module - 在 OCaml 中，是否可以根据 Set 定义 Map？

Question

我已经在 OCaml 中实现了集合(平衡搜索树)的表示。它实际上是一个仿函数 Make签名的

module Make :
  functor (T : ORDERED_TYPE) ->
sig
  type elt = T.t
  type t
  val empty : t
  val cons : elt -> t -> t
  val delete : elt -> t -> t
  val mem : elt -> t -> bool
  val cardinal : t -> int
end

在哪里

 module type ORDERED_TYPE = sig type t val compare : t -> t -> int end

现在我想实现一个像 Map 这样的字典。在标准库中。它必须有一个像这样的签名

 module Make: functor (T : ORDERED_TYPE) -> sig
    type key = T.t
    type +'a t
    ...
 end

在哪里 t是字典的类型。

再次实现平衡搜索树并不优雅，所以我想根据上面实现为仿函数的集合来定义字典。我可以这样做吗？

Answer 1

正如 Jeffrey 所说，您 Set接口(interface)不够表达，无法方便地实现Map在它的上面。实现 Set 会更简单来自 Map ，通过将集合定义为从键到单位值的映射。

我建议的另一种可能性是，首先公开一个没有封装的平衡搜索树模块，其唯一目的是提供一个完全由接口(interface)显示的有效数据结构。然后，您可以自由地将它重用于您喜欢的任何数据结构，包括 Map和 Set ，而不必玩游戏来定义另一个。在这种情况下，这可能不是非常重要(从 Set 定义 Map 对于大多数用途来说是合理的)，但在我看来，在一般情况下这是一个更好的设计。

简而言之:如果你想重用实现，那么暴露“实现模块”，并在它们之上定义你的“接口(interface)模块”。