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

我已经在OCaml中实现了集合（平衡搜索树）的表示。它实际上是签名在OCaml中，是否可以根据Set定义Map？

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字典的函子Make。它必须有一个像

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

其中t是字典的类型。

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

来源

2012-04-29 Pteromys

对我来说，映射是一个（部分）函数，它是一组有序对。如果你正确地定义你的比较函数，我认为它可以完成。您可能需要在Set接口中添加一个函数，以说明两个值可以为成员资格而比较相等，但实际上并不相等。使用当前接口定义映射的查找函数似乎是不可能的。

来源

2012-04-29 06:21:15

正如杰弗里指出的那样，您的Set界面不够充分表达，无法在其上实现Map。通过将集合定义为从键到单位值的映射，从Map实施Set会更简单。

我推荐的另一种可能性是首先公开一个平衡搜索树模块而没有封装，其唯一目的是提供一个有效的数据结构，这完全由接口显示。然后，您可以自由使用任何您喜欢的数据结构，包括Map和Set，而无需玩游戏来定义其他游戏。在这种情况下，这可能并不是非常重要（在0123.中定义Set对于大多数用途来说是合理的），但在我看来这是一般情况下更好的设计。简而言之：如果你想重用实现，然后公开“实现模块”，并在其上定义你的“接口模块”。

来源

2012-04-29 07:53:25 gasche

问题是作业的陈述似乎要求我用Set来定义Map非常模糊的单词。顺便说一句，如果我尝试将结构传递给Set，那么我必须定义类型t，但我该怎么做呢？我想吨是多态的类型。 – Pteromys 2012-04-29 08:02:44

正如其他人已经指出，至少有两方面的原因，为什么你不能执行所请求的地图仿函数在给定的顶部：

该组特征提供了没有办法找到的“相等“的元素。
即使这样做，您也无法以多态方式将值存储在那里，因为类型'a map似乎需要。

您确定该任务需要您在集之上实施地图吗？也许你只是应该执行他们像集？

来源

2012-04-29 09:36:39

那么，实际上有一个等于运算符那里 - 比较函数从有序的类型。

所以定义自己的模块，一键/值类型，只有考虑到比较关键的部分：

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

和你做。现在的问题是，你的设置不允许你得到它的值;没有获得也没有折叠函数 - 哪些imho真的限制这样的数据结构。如果你被允许与设置实施摸索，你需要添加一个得到功能：

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

将返回刚才问的元素。如果您拿到返回元组的第二个元素，那么您的值与原始键/值对有关。

来源

2012-05-02 13:08:28 lambdapower

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

回答

相关问题