在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

在我看来，地图是一个（部分）函数，它是一组有序对。如果您正确定义比较函数，我认为这是可以完成的。您可能需要向 Set 接口添加一个函数，以考虑到两个值可以出于成员资格目的进行比较，但实际上不是相等的值。目前的接口似乎无法定义地图的查找功能。