Functor 没有正确地继承签名

Question

我正在使用 OCaml 开发布隆过滤器，但我真的很困惑。

首先，我定义了一个与布隆过滤器交互的签名，这样布隆过滤器可以通过多种不同的方式实现：

module type memset = sig
    type elt (* type of values stored in the set *)
    type t (* abstract type used to represent a set *)
    val mem : elt -> t -> bool
    val empty : t
    val is_empty : t -> bool
    val add : elt -> t -> t
    val from_list : elt list -> t
    val union : t -> t -> t
    val inter : t -> t -> t
  end

布隆过滤器目前有两种实现方式：

稀疏集
SparseSet 是通过使用列表存储所有整数来实现的。

module SparseSet : (memset with type elt = int) = struct
    include Set.Make(struct
        let compare = Pervasives.compare
        type t = int
    end)

    let from_list l = List.fold_left (fun acc x -> add x acc) empty l
end

布尔集
通过存储一个布尔数组来实现布隆过滤器，其中如果对应的索引 = true，则整数是集合的成员。

module BoolSet : (memset with type elt = int) = struct
    type elt = int
    type t = bool array

    (* implementation details hidden for clarity's sake *)
  end

为了存储不是整数的项是否存在于集合中，我定义了一个hasher签名：

module type hasher = sig
    type t (* the type of elements that are being hashed *)
    val hashes : t -> int list
end

最后，我定义了一个接受布隆过滤器实现和哈希器的过滤器仿函数。要添加一个项目，使用三种不同的方法对一个项目进行哈希处理以产生 3 个整数。这三个整数存储在传递给 Filter 仿函数的底层 memset 模块中。要检查集合中是否存在某个项目，需要获取并检查其 3 个哈希值。如果集合中存在所有三个散列整数，则该项目包含在集合中。 filter functor允许bloom set的实现，hash方法换出：

module Filter (S : memset) (H : hasher)
    : memset
    with type elt = H.t
    with type t = S.t = struct

    type elt = H.t
    type t = S.t

    let mem x arr = [] = List.filter (fun y -> not (S.mem y arr)) (H.hashes x)
    let empty = S.empty
    let is_empty = S.is_empty
    let add x arr = List.fold_left (fun acc x -> S.add x acc) empty (H.hashes x)
    let add x arr = empty
    let from_list l = S.from_list l
    let union l1 l2 = S.union l1 l2
    let inter l1 l2 = S.inter l1 l2
  end

当我尝试编译这个程序时，我在 Filter 仿函数的 mem、add 和 from_list 函数处出现以下编译时错误：

File "bloom.ml", line 75, characters 66-78:
Error: This expression has type int list but an expression was expected of type
         S.elt list
       Type int is not compatible with type S.elt

由于某种原因，该类型未在过滤器模块中正确传递。有人对如何解决此问题有任何建议吗？我一直在绞尽脑汁想弄明白。

Answer 1

行

module Filter (S : memset) (H : hasher) = ...

意味着仿函数应该适用于任何 memset，独立于元素的类型 S.elt。但是，仿函数主体假定 S.elt 是 int，导致类型错误：

 Type int is not compatible with type S.elt

您可以通过在参数签名中确定 S.elt 的类型来解决此问题：

module Filter (S : memset with type elt = int) (H : hasher) = ...

Functor 没有正确地继承签名

Functor does not properly inherit signature

ocaml

caml