SML/NJ: Как использовать HashTable?

Question

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

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

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

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.