Я работаю над фильтром Блума в 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
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
BoolSet
Реализация фильтра Блума выполняетсяхранение массива логических значений, где целое число является членом набора, если его соответствующий индекс = 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 целых числа.Три целых числа хранятся в базовом модуле memset, передаваемом в функтор Filter.Чтобы проверить, существует ли элемент в наборе, его 3 хеша получены и проверены.Если в наборе есть все три хеш-числа, элемент содержится в наборе.Функтор фильтра позволяет реализовать набор Блума и поменять метод хеша:
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
Когда я пытаюсь скомпилировать эту программу, я получаю следующую ошибку во время компиляции, которая возникает в * 1027Функции *, 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
По какой-то причине тип не проходит правильно в модуле фильтра.У кого-нибудь есть предложения, как это исправить?Я рвал на себе волосы, пытаясь понять это.