The SML/NJ Library includes a variety of data structures, and several
interfaces for abstract data types. For complete documentation go
here. Below we provide extra information for the more frequently used
data structures. You can get access to the SML/NJ Library by including ` smlnj-lib.cm`
in your

We saw implementations of sets and maps (which we called dictionaries) in class, but in problem sets and in general, it is better to use the efficient implementations provided as one of the libraries in Standard ML of New Jersey. They are based on fully functional Red-Black trees, which are balanced binary trees. We will see Red-Black trees later in the course, and discuss why they are efficient.

The SML/NJ library provides functors to construct sets and maps over any type for which a compare function can be defined, in a way similar to what we did in class.

To create a structure implementing sets over a type *T* with an
operation *compareT*, we use the declaration:

structure SetT = RedBlackSetFn (struct type ord_key =Tval compare =compareTend)

The resulting structure has the signature *ORD_SET*.

Note that one operation that is typically need for sets is one to efficiently
choose an arbitrary element from a set. This can be achieved by calling *find
(fn _ => true)* on a particular set from which we want to choose.
Intuitively, this operation finds the first element of the set for which the
predicate *fn _ => true* returns true, which happens immediately.

To create a structure implementing maps (dictionaries) over a type *T*
with an operation *compareT*, we use the similar declaration:

structure MapT = RedBlackMapFn (struct type ord_key =Tval compare =compareTend)

The resulting structure has the signature *ORD_MAP*.

Hash tables all have the signature *HASH_TABLE*.

The following is from a newsgroup posting (we'll make this discussion more professional later on):

Insert and find should be pretty apparent. Lookup is just like find, but it raises an exception (see below) when it can't find the key you gave it. The tricky thing is mkTable. Here's an example where I'm using a hash table to map strings to integers: open HashTable (* raised when I do a lookup and can't find something *) exception Can't_Find_It (* used to convert a string to a hash code -- i.e., word *) val hash_fn : string->word = HashString.hashString (* used to compare keys in the hash table *) fun cmp_fn : string*string->bool = (op =) (* initial table size -- need something relatively prime and * approximately the size of the number of elements you expect * to be in the hash table. Note that the implementation resizes * as needed to avoid major collisions. *) val initial_size : int = 101 val t : (string,int) table = mkTable (hash_fn, cmp_fn) (initial_size, Can't_Find_it) So, I passed in to mkTable (1) a function for converting keys to hash codes (words), (2) a function for comparing keys (cmp_fn), (3) an initial size for the table, (3) an exception to raise when the hash table can't find a key upon lookup. Now I can insert string*int pairs into my table: insert t ("Greg",33); insert t ("Amy",3); insert t ("John",1); and I can look them up by key (i.e., string): lookup t "Greg" (* should evaluate to 33 *) lookup t "Amy" (* should evaluate to 3 *) If I give it a key that's not in the table, then the exception I passed in to mkTable (Can't_Find_it) will be raised: lookup t "Raymond" (* should raise Can't_Find_it *)

A fairly thorough discussion of hash tables in SML/NJ can be found here.