SML/NJ: Como usar hashtable?

Question

Eu realmente quero criar uma hashtable no SML, parece que já existe uma estrutura para isso no SML/NJ.

A questão é: como faço para usá -lo? Não entendi totalmente como usar estruturas na SML, e alguns dos exemplos muito básicos do livro que li me dão erros que nem sei como corrigir, portanto, usar a estrutura de hashtable pode ser uma coisa fácil, mas Eu não saberia. Se alguém pudesse explicar isso, isso também seria maravilhoso!

Estou pensando que é algo assim:

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

???

Answer 1

A assinatura do mkTable O valor é:

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

Portanto, você teria que fazer algo como:

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

Answer 2

Suponho que a idéia é criar uma tabela mapeando strings para inteiros. Então você quer escrever seu tipo como (string, int) hash_table (o tipo hash_table é um tipo com dois parâmetros, que são escritos assim em ML).

Mas você também precisa de uma função de hash hash : string -> word e uma função de igualdade eq : string * string -> bool sobre cordas para fornecer a mkTable. Para este último, você pode simplesmente usar op=, para o primeiro que você pode usar HashString.hashString Do respectivo módulo.

Então,

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

Deveria trabalhar.

Devo observar, no entanto, que as tabelas de hash tendem a ser muito usadas e, na maioria das vezes, são a estrutura de dados errados. Isso é especialmente verdadeiro na programação funcional, pois são uma estrutura de dados com estado. Geralmente você está melhor (e potencialmente ainda mais eficiente) usando algum mapa baseado em árvores, por exemplo, o RedBlackMapFn Na biblioteca SML/NJ.