SML/NJ Library

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 in your file.

Sets and Maps

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 = T
                                  val compare = compareT

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 = T
                                  val compare = compareT

The resulting structure has the signature ORD_MAP.

Hash Tables

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.