SML/NJ: Come usare l'hashtable?

Question

Voglio davvero creare un hashtable in SML, sembra che ci sia già una struttura per questo in SML/NJ.

La domanda è: come lo uso? Non ho capito completamente come usare le strutture in SML, e alcuni degli esempi di base nel libro che ho letto mi danno errori che non so nemmeno come correggere, quindi usare la struttura hashtable potrebbe essere una cosa facile, ma Non lo saprei. Se qualcuno potesse spiegarlo, anche quello sarebbe meraviglioso!

Sto pensando che sia qualcosa di simile:

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

???

Answer 1

La firma del mkTable Il valore è:

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.
     *)

Pertanto, dovresti fare qualcosa di simile:

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

Answer 2

Presumo che l'idea sia quella di creare una tavola mappatura delle stringhe agli interi. Allora vuoi scrivere il suo tipo come (string, int) hash_table (Il tipo hash_table è un tipo con due parametri, che sono scritti come quello in ML).

Ma hai anche bisogno di una funzione hash hash : string -> word e una funzione di uguaglianza eq : string * string -> bool oltre le corde da fornire a mkTable. Per quest'ultimo, puoi semplicemente usare op=, per il primo puoi usare HashString.hashString Dal rispettivo modulo.

Così,

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

dovrebbe funzionare.

Dovrei notare, tuttavia, che le tabelle di hash tendono ad essere ampiamente abusate e il più delle volte sono la struttura dei dati sbagliata. Ciò è particolarmente vero nella programmazione funzionale, poiché sono una struttura di dati statali. Di solito stai meglio (e potenzialmente ancora più efficiente) usando una mappa basata su alberi, ad esempio, il RedBlackMapFn Dalla libreria SML/NJ.