polymorphism - OCaml：具有通用键的地图上的多态函数

Question

在 OCaml 中，通用地图上有多态函数吗？IE：

你可以有：f : 'a list -> bool相当于bool f<T> ([T] x)

你也可以有类似f : ('k,'v) map -> bool的东西：相当于bool f<K,V> (Map<K,V> x)？

如果是这样，类型签名的正确语法是什么，以及如何实现这样的函数（我问，因为 map 是抽象类型，操作它的唯一方法是使用通过调用Map.Make具体类型获得的函数)?

谢谢

Answer 1

这取决于您使用哪种类型的通用映射，并且您必须区分这两个参数（键的类型和值的类型）。如果你使用默认库的Map.Make 仿函数，你可以在值的类型上通用，但是键的类型将是固定的（通过仿函数实例化）：对于给定的键模块Key，生成的映射module MyMap = Map.Make(Key)只有一个参数，'v MyMap.t，所以你可以有f : 'v MyMap.t -> bool。

还有其他库提供所谓的“多态”映射，其形式类型('k, 'v) pmap允许在键和值类型上都是多态的。然而，这通常是以较少的静态保证为代价的：如果您以'k一种不保留键顺序的方式进行更改，您将获得不一致的结果，而这种方式在编译时无法检测到。

当然，您可以通过增强Map.Make函子本身来实现适用于任何键类型的附加功能（代码未经测试）：

module MyMake(K : Map.OrderedType) = struct
  include Map.Make(K)
  (* after the "include", all the functions provided by `Map.Make`
     are available in the module *)
  let is_not_empty m = not (is_empty m)
end

module MyMap = MyMake(String)
let foo = MyMap.is_not_empty (...)

（备注：如果您不需要持久性集合（不复制/共享/回溯值）并且您不关心最坏情况的复杂性（无用暴露于用户拒绝服务攻击），您可以也可以使用哈希表，使用提供类型的Hashtbl('k, 'v) Hashtbl.t模块。但是'k实际上并不存在多态性：您没有任何函数可以使该参数发生变化）。