如何约束Hashable模块的key类型与签名中的type参数相同？

Question

我有一个可变集的签名：

open Base
open Hashable

module type MutableSet = sig
  type 'a t
  val contains : 'a t -> 'a -> bool
end

我想使用 Base 库中的 Hashable 模块通过 HashSet 实现签名。

module HashSet(H : Hashable) : MutableSet = struct
  let num_buckets = 16
  type 'a t = { mutable buckets : ('a list) array }
  let contains s e =
    let bucket_index = (H.hash e) % num_buckets in
    let bucket = s.buckets.(bucket_index) in
    List.exists ~f:(fun e' -> H.equal e e') bucket
end

我遇到错误

Error: Signature mismatch:
       Modules do not match:
         sig
           type 'a t = { mutable buckets : 'a list array; }
           val contains : 'a H.t t -> 'a H.t -> bool
         end
       is not included in
         MutableSet
       Values do not match:
         val contains : 'a H.t t -> 'a H.t -> bool
       is not included in
         val contains : 'a t -> 'a -> Base.bool

我认为问题在于 Hashable 键的类型不限于与集合中元素的类型 'a 相同。如何将类型限制为相同？

Answer 1

module HashSet(H : Hashable) : (MutableSet with type t = H.t)

这个，我猜。不过目前无法检查。

Answer 2

问题是

中的等式H.equal

List.exists ~f:(fun e' -> H.equal e e') bucket

是散列函数字典 ('a H.t) 上的等式。因此，如所写，contains 函数仅适用于散列函数字典集。如果你想要一个多态可变集，你将不得不使用多态相等。

Answer 3

问题的症结在于 H.equal 函数，其类型为 'a t -> 'a t -> bool，请参见 H.hash 的类型为 'a -> int。我认为一切都出错了，因为你对 Base 中 hashable 的含义有错误的假设。 Hashable.t类型是三个函数的记录，定义如下¹:

type 'a t = { 
  hash : 'a -> int;
  compare : 'a -> 'a -> int;
  sexp_of_t : 'a -> Sexp.t;
}

因此，任何想要可哈希的类型都必须提供这三个函数的实现。尽管有一个模块类型 Hashable ，但它并不是设计用来作为仿函数的参数的。只有一个 Hashable 模块，它定义了可哈希值的接口（如果需要，可以输入 class）。

因此，如果您需要一个单态 MutableSet 用于可散列的键，您应该编写一个仿函数，它采用 Hashable.Key.

类型的模块

module HashSet(H : Hashable.Key) = struct
  let num_buckets = 16
  type elt = H.t
  type t = { mutable buckets : H.t list array }

  let contains s e =
    let bucket_index = H.hash e % num_buckets in
    let bucket = s.buckets.(bucket_index) in
    List.exists ~f:(fun e' -> H.compare e e' = 0) bucket
end;;

如果你想实现一个多态的 MutableSet，那么你不需要写一个仿函数（如果它是多态的，那么它已经为所有可能的类型定义了.)。您甚至可以使用 Hashable 模块本身的多态函数，例如

module PolyHashSet = struct
  let num_buckets = 16
  let {hash; compare} = Hashable.poly

  type 'a t = { mutable buckets : 'a list array }

  let contains s e =
    let bucket_index = hash e % num_buckets in
    let bucket = s.buckets.(bucket_index) in
    List.exists ~f:(fun e' -> compare e e' = 0) bucket
end

follow-up 个问题的答案

When would you want to use Hashable.equal to compare two type classes?

1) 当需要保证两个hashtable使用的是同一个比较函数时。例如，如果你想合并两个 table 或交叉两个 table，它们应该使用相同的 comparison/hash 函数，否则，结果是不确定的。

2) 当你需要比较两个散列table是否相等时。

Is there a way to define the polymorphic version without using the built in polymorphic hash functions and equals methods?

如果"built-in"你的意思是OCaml提供的原语，那么答案是，不，这样的散列table必须使用OCaml标准库中的多态比较原语。

您不必使用基础库中的 Hashable 模块来访问它们。它们也可以通过 Base 中的 Caml 或 Polymorphic_compare 模块获得。或者，如果您不使用 Base 或 Core 库，则默认情况下来自 Stdlib 的 compare 函数是多态的并且类型为 'a -> 'a -> int.

综上所述，我认为需要对我们所说的多态版本进行一些澄清。 Base 的 Hash_set 以及 Hashtbl 也是多态数据结构，因为它们对应地具有类型 'a t 和 ('k,'a) t，它们的键都是多态的。然而，它们不依赖于多态比较函数，而是需要用户在构造期间提供比较函数。事实上，它们需要 hashable 接口的实现。因此，要创建一个空散列 table，您需要向它传递一个实现它的模块，例如，

let empty = Hashtbl.create (module Int)

其中传递的模块必须实现 Hashable.Key 接口，这超出了其他模块通过 Hashable.of_key 函数提供 hashable 的实现。而 hashtable 实现只是将比较函数存储在自身中，例如，粗略地说，

type ('a,'k) hashtbl = {
  mutable buckets : Avltree.t array;
  mutable length : int;
  hashable : 'k hashable;
}

我认为，鉴于此实现，现在我们需要与可散列记录进行比较时会更加明显。

Is one version (monomorphic with Functor vs polymorphic) preferable over the other?

首先，我们其实有三个版本。 Functor，多态的，以及使用多态比较函数的函数（我们将其命名为 universal）。后者是最不受欢迎的，应尽可能避免。

关于前两者，两者都很好，但多态版本更通用，不会涉及太多妥协。从理论上讲，仿函数版本为编译器优化提供了更多机会（因为可以内联比较函数），但它的代价是每个键都有不同的 module/type。

您还可以从这两种方法中受益，并提供多态和单态实现（后者是前者的特化），例如，这就是 JS 中映射和集合的实现方式 Base/Core。有一个集合的多态类型，

type ('a,'comparator_witness) set

是二叉树加上比较函数，通过'comparator_witness类型体现在集合类型中，这样每一个比较函数都会生成一个全新的类型，从而防止Set.union 等两个集合之间的操作，其中存储了不同的比较函数。

同时还有一个 Set.Make(K : Key) 仿函数，它创建一个提供 type t = (K.t,K.comparator_witness) set 类型的模块，理论上可以从内联中获益。此外，每个实现 Core.Comparable.S 及以下的模块，还将提供 .Map、.Set 等模块，例如 Int.Set。这些模块通常是通过相应的 Make 仿函数（即 Map.Make、Set.Make）创建的，但它们为手动专业化提供了机会。

1) 因此 Hashable.equal 函数实际上比较函数而不是值。它基本上比较两种类型 classes。而且，我相信 Hashable.hash 函数是不小心输入了 'a -> int，而预期的类型也是 'a t -> int。

如何约束Hashable模块的key类型与签名中的type参数相同？

How do I constrain the key type of the Hashable module to be the same as the type parameter in the signature?

ocaml

functor

ocaml-core

follow-up 个问题的答案