SML/NJ : Hashtable을 사용하는 방법?

Question

나는 SML에서 Hashtable을 만들고 싶다. 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 라이브러리에서.