5

我已经在 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是字典的类型。

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

4

4 回答 4

4

正如 Jeffrey 所指出的，您Set的接口不够富有表现力，无法Map在其之上方便地实现。通过将集合定义为从键到单位值的映射，实现Setfrom会更简单。Map

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

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

于 2012-04-29T07:53:25.017 回答
3

在我看来，地图是一个（部分）函数，它是一组有序对。如果您正确定义比较函数，我认为可以完成。您可能必须向 Set 接口添加一个函数，以说明两个值可以出于成员资格比较相等但实际上不是相等的值这一事实。使用当前界面似乎无法定义地图的查找功能。

于 2012-04-29T06:21:15.507 回答
2

正如其他人已经指出的那样，您不能在给定集合之上实现请求的映射函子至少有两个原因：

  1. 集合签名无法在给定集合中找到“相等”元素。
  2. 即使它这样做了，你也不能像类型'a map似乎需要的那样多态地在其中存储值。

您确定该任务需要您在集合之上实现地图吗？也许您应该像集合一样实现它们？

于 2012-04-29T09:36:39.577 回答
0

好吧，实际上有一个相等的运算符——来自有序类型的比较函数。

因此，为仅比较键部分的键/值类型定义您自己的模块：

module Keyvalue = struct
   type t = ('a * 'b)
   let compare x y = Pervasives.compare (fst x) (fst y)
end

你就完成了。现在的问题是，您的Set不允许您获取其值；没有get也没有fold函数——恕我直言，这确实限制了这种数据结构。如果允许您摸索Set实现，则需要添加一个get函数：

module Set = sig
   ...
   get : t -> elt -> elt
end

这将返回刚刚要求的元素。如果您获取返回元组的第二个元素，您将获得来自原始键/值对的值。

于 2012-05-02T13:08:28.393 回答