使用第一类模块对集合进行索引
使用第一类模块对集合进行索引
提问于 2014-10-01 02:31:31
假设我想对集合中的所有元素进行索引，并将此索引存储在映射中。一个可行的解决方案是扩展Set模块并创建一个内部functor：
module Make(M : Set.S) = struct
include M
module MakeIndexer(MM : Map.S with type key = elt) = struct
let index_set set =
let aux el (ix, acc) =
(ix + 1, MM.add el ix acc)
in
M.fold aux set (0, MM.empty) |> snd
end
end现在，内部函数器的使用有点麻烦，我想使用一个使用第一类模块的实现。到目前为止，我得到了以下信息：
module Make(M : Set.S) = struct
include M
let index_map (module MM : Map.S with type key = elt) set =
let aux el (ix, acc) =
(ix + 1, MM.add el ix acc)
in
M.fold aux set (0, MM.empty) |> snd
end我得到了以下错误信息
Characters 156-191:
M.fold aux set (0, MM.empty) |> snd
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: This expression has type int MM.t
but an expression was expected of type int MM.t
The type constructor MM.t would escape its scope我知道我使用的是语法糖，并且模块在函数中是本地绑定的，但是有没有办法使用第一类模块来编写函数呢？
回答 2
Stack Overflow用户
发布于 2014-10-01 02:50:38
更新的版本
如果我没理解错的话，你想让索引映射算法polymorhic w.r.t映射到结构。实际上，从整个Map操作集中只需要两件事:初始值和加法运算符。所以你可以把它们作为参数传递给你的函数。
module Make(T : Set.OrderedType) = struct
module Set = Set.Make(T)
let index_map (set : Set.t) (map : 'm) add : 'm =
let aux el (ix, acc) =
(ix + 1, add el ix acc) in
Set.fold aux set (0, map) |> snd
endStack Overflow用户
发布于 2014-10-01 21:51:38
使用数组
假设我想对集合中的所有元素进行索引，并将此索引存储在映射中。
您的解决方案过于复杂。
您应该改用包含集合元素的数组。如果按递增顺序排序，则可以在O(log )中找到项目的索引-这与映射提供的内容一样好-并且可以在O(1)中找到绑定到索引的项目-映射不提供此功能。
使用数组将更容易描述，更容易实现，并以相同的性能提供更多的功能:这是一次彻底的胜利。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/26127691
复制相关文章
相似问题
腾讯云开发者
