Суть проблемы - функция H.equal, которая имеет тип 'a t -> 'a t -> bool, ср., С H.hash, которая имеет тип 'a -> int.Я думаю, что все пошло не так из-за ваших неверных предположений о том, что означает хэши в Base.Тип Hashable.t является записью трех функций и определяется следующим образом: 1 :
type 'a t = {
hash : 'a -> int;
compare : 'a -> 'a -> int;
sexp_of_t : 'a -> Sexp.t;
}
Поэтому любой тип, который хочет быть хэшируемым, должен обеспечивать реализацию этих трехфункции.И хотя существует тип модуля модуля Hashable, он не предназначен для использования в качестве параметра функтора.Существует только один модуль Hashable, который определяет интерфейс (класс type, если вы хотите) значения hashable.
Поэтому, если вам нужен мономорфный 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
Ответы на последующие вопросы
Когда вы захотите использовать Hashable.equal длясравнивать два типа классов?
1) Когда необходимо убедиться, что две хеш-таблицы используют одну и ту же функцию сравнения.Например, если вы хотите объединить две таблицы или пересечь две таблицы, они должны использовать одни и те же функции сравнения / хеш-функции, в противном случае результаты не определены.
2) Когда вам нужно сравнить две хеш-таблицы на равенство.
Есть ли способ определить полиморфную версию без использования встроенных полиморфных хеш-функций и методов равенства?
Если под «встроенным» вы имеете в виду примитивы, предоставленные OCaml, то ответ: нет, такая хеш-таблица должна использовать полиморфный примитив сравнения из стандартной библиотеки OCaml.
Youне нужно использовать модуль Hashable из базовой библиотеки, чтобы получить к ним доступ.Они также доступны через Caml или Polymorphic_compare модулей в Base.Или, если вы не используете библиотеки Base или Core, то функция compare из Stdlib по умолчанию является полиморфной и имеет тип 'a -> 'a -> int.
. После всего сказанного, я думаю, что некоторые пояснениянужен на то, что мы говорим по полиморфной версии.Hash_set в Base, как и Hashtbl, также являются полиморфными структурами данных, так как они имеют типы 'a t и ('k,'a) t соответственно, которые оба полиморфны в своих ключах.Они, однако, не полагаются на полиморфную функцию сравнения, но требуют, чтобы пользователь предоставил функцию сравнения во время построения.Фактически, они требуют реализации интерфейса hashable.Поэтому, чтобы создать пустую хеш-таблицу, вам нужно передать ей модуль, который ее реализует, например,
let empty = Hashtbl.create (module Int)
, где переданный модуль должен реализовать интерфейс Hashable.Key, который помимо других обеспечивает реализацию hashable через функцию Hashable.of_key.И реализация с хеш-таблицей просто хранит функции сравнения в себе, например, примерно,
type ('a,'k) hashtbl = {
mutable buckets : Avltree.t array;
mutable length : int;
hashable : 'k hashable;
}
Я думаю, что с учетом этой реализации теперь стало более очевидно, когда нам нужно сравнить с хэш-записями.
Является ли одна версия (мономорфная с Functor vs polymorphic) предпочтительнее другой?
Прежде всего, у нас фактически есть три версии.Функтор, полиморфный и тот, который использует полиморфную функцию сравнения (назовем ее универсальной).Последнее имеет наименьшее предпочтение, и его следует избегать, если это возможно.
Относительно первых двух, оба хороши, но полиморфная версия более универсальна, без большого количества компромиссов.Теоретически, версия с функтором открывает больше возможностей для оптимизации компилятора (поскольку функция сравнения может быть встроена), но она имеет цену, что для каждого ключа у вас будет свой модуль / тип.
Вы также можете извлечь выгоду из обоих подходов и предоставить как полиморфные, так и мономорфные реализации (причем последняя является специализацией первой), например, именно так карты и наборы реализуются в 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 фактически сравнивает функции, а не значения.Это в основном сравнивает два типа классов.И, я полагаю, функция Hashable.hash была набрана 'a -> int случайно, и предполагаемый тип был также 'a t -> int.