给定一个绑定，找到映射中的键的简单方法，Ocaml

Question

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

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

- SoftTimur

Answer 1

如果这是一次不经常发生的操作，最简单的方法是对地图 SMap.fold 的所有(key,value)绑定进行折叠:

# 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>

如果这是常见操作，您需要的是一个双向映射（可以在两个“方向”上查询的映射）。最简单的方法是携带一对映射：int IMap.t * string SMap.t（在两个方向上的访问都是对数级别的，而reverse在映射大小上是线性的）。您也可以实现一个专用数据结构，但这可能不值得增加复杂性。

PS：reverse可以优化以便在找到值时提前退出迭代，但如果它是不常见的操作，则并不重要。

- gasche