Back to the PSciCo homepage



TABLE defines an interface for manipulating tables of type 'a table that stores values of type 'a keyed on keys of type key. The interface supplies functions for searching, insertion, deletion, intersection, as well as many other things. There are currently three implementations, which use Treaps, Splay Trees, and Red-Black Trees.

Relevant Files

  • TABLE.sml: Defines the interace.
  • RedBlackTable.sml: Implementation based on red-black trees.
  • TreapTable.sml: Implementation based on splay trees.
  • SplayTable.sml: Implementation based on treaps.
  • IntTable.sml: A table based on treaps using int keys.
  • CHANGES.txt: The change log for this library.

  • Description

    The TABLE interface is similar to the ORD_MAP interface from the SML/NJ Library. It however has several additional features.

    First it supplies a generalized update function, generalUpdate, which can be used to implement search, insert or delete as well as many other combinations. For example, it can be used to update the value associated with a key while returning the old value, or conditionally delete a value. These operations would require two operations and hence two searches through the data-structure in a standard purely functional interface (such as ORD_MAP). With the generalUpdate they only require a single search.

    There is also a slightly more specific function update that can update the value of a key in the same way as genUpdate, but it will not return a value. This, for example can be used to implement insert as follows:

        fun insert(key, value, table) = 
           update (fn _ => SOME(value)) (key, table) 
    Alternatively you could define a version that raises an exception if the item is already in the table:
        fun insert(key, value, table) = 
           update (fn SOME(_) => raise alreadyThereException
                    | NONE    => SOME(value)) 
           (key, table) 
    As another example, if you wanted to delete an item if it is in the table but add it if it is not, you could implement this as:
        fun insertDelete(key, value, table) = 
           update (fn SOME(_) => NONE
                    | NONE    => SOME(value)) 
                  (key, table) 

    Also, in addition to intersect and union, there is a diff function.


    The PSCICO project is supported by NSF under the title "Advanced Languages for Scientific Computation Environments" as part of the Experimental Software Systems program within CISE. The grant number is 9706572.

    Back to the PSciCo homepage.