polymorphism - OCaml:具有通用键的 map 上的多态函数

Question

在 OCaml 中，通用映射上是否有多态函数？即:

你可以有: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) 生成的 map 只有一个参数，'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 (...)

(备注:如果您不需要持久集合(没有值的复制/共享/回溯)并且您不关心最坏情况的复杂性(没有使用暴露给用户拒绝服务攻击) ，你也可以使用哈希表，通过提供 ('k, 'v) Hashtbl.t 类型的 Hashtbl 模块。但是 'k 上的多态性并不真正存在:你没有得到任何可以使这个参数变化的函数)。