SML/NJ: Как использовать хэш -таблицу?

Question

Я действительно хочу создать хэштату в SML, кажется, что в SML/NJ уже есть структура.

Вопрос в том, как мне его использовать? Я не до конца понял, как использовать структуры в SML, и некоторые из самых основных примеров в книге, которую я читаю Я бы не знал. Если бы кто -то мог это объяснить, то это тоже было бы замечательно!

Я думаю, что это что -то вроде этого:

val ht : string * int HashTable.hash_table = HashTable.mkTable();

???

Answer 1

Подпись mkTable ценность:

val mkTable : (('a -> word) * (('a * 'a) -> bool)) -> (int * exn)
      -> ('a,'b) hash_table
    (* Given a hashing function and an equality predicate, create a new table;
     * the int is a size hint and the exception is to be raised by find.
     *)

Поэтому вам придется сделать что -то вроде:

val ht : (string, int) HashTable.hash_table =
    HashTable.mkTable (HashString.hashString, op=) (42, Fail "not found")

Answer 2

Я предполагаю, что идея состоит в том, чтобы создать строки сопоставления таблицы для целых чисел. Тогда вы хотите написать его тип как (string, int) hash_table (Тип hash_table это тип с двумя параметрами, которые написаны так в ML).

Но вам также нужна хэш -функция hash : string -> word и функция равенства eq : string * string -> bool над строками, чтобы обеспечить mkTable. Анкет Для последнего вы можете просто использовать op=, для первого вы можете использовать HashString.hashString Из соответствующего модуля.

Так,

val ht : (string, int) HashTable.hash_table = HashTable.mkTable(HashString.hashString, op=)(17, Domain)

должно сработать.

Однако я должен отметить, что хэш -таблицы, как правило, чрезмерно чрезмерно используются, и чаще всего они являются неправильной структурой данных. Это особенно верно в функциональном программировании, поскольку они являются современной структурой данных. Обычно вам лучше (и потенциально еще более эффективно), используя какую-то карту на основе дерева, например, RedBlackMapFn из библиотеки SML/NJ.