map - 在给定绑定(bind)的 map 中查找键的简单方法，Ocaml

Question

我对Ocaml中的Map模块不是很熟悉。

我有一个简单的映射 m: string Map.Make(Int).t 从 int 到 string，我知道每个绑定(bind) (:string) 是唯一的。我想写一个函数 find_from_string_to_int: string -> string Map.Make(Int).t -> int，有人能帮忙吗？非常感谢!

Answer 1

如果这是一个不常见的操作，最简单的方法是折叠 map SMap.fold 的所有(键，值)绑定(bind):

# module SMap = Map.Make(String);;
# let reverse v t =
  SMap.fold (fun k v' acc -> if v = v' then Some k else acc) t None;;
val reverse : 'a -> 'a SMap.t -> SMap.key option = <fun>

如果这是一个普通的操作，你要找的是一个双向 map (一个可以在两个“方向”上查询的 map )。最简单的方法是携带一对映射:int IMap.t * string SMap.t(双向访问是对数的，而上面的reverse是线性的 map 的大小)。您也可以实现专用的数据结构，但这可能不值得增加复杂性。

PS:reverse 可以优化为在找到值时尽早退出迭代，但如果它是一个不常见的操作，那么无论如何它都不是很重要。