GIML: Using Structures

The New Jersey Library

This library is distributed with the New Jersey version of ML. On my system this can be found in the directory /usr/local/lib/smllib It contains a number of signatures, structures and functors which are likely to be useful to programmers.

The five files referred to in this example are:

Using a dictionary

A dictionary is a massively useful thing to have in many situations. (Also known as tables in relational database terminology & associative arrays). The basic idea is that data can be associated with a key value.

We wish to store an internal telephone directory and allow fast access:

Departmental Directory
Key	Room Number	Telephone
alison	238	4218
andrew	236	4677
gordon	236	4677

We could store this as a list of tuples:

[("alison",(238,4218)),("andrew",(236,4677)),("gordon",(236,4677))]

however looking up data in a simple list is costly - on average half the list must be examined to find a particular item. There are many methods which trade off the cost of adding data against the cost of accessing data - rather than do this work ourselves we rely on the excellent work of others.

The signature DICT describes the access functions as follows:

signature DICT = sig structure Key : ... type 'a dict exception NotFound val mkDict : unit -> '1a dict val insert : '1a dict * Key.ord_key * '1a -> '1a dict val find : 'a dict * Key.ord_key -> 'a val peek : 'a dict * Key.ord_key -> 'a option val remove : '1a dict * Key.ord_key -> '1a dict * '1a val numItems : 'a dict -> int val listItems : 'a dict -> (Key.ord_key * 'a) list val app : (Key.ord_key * 'b -> 'a) -> 'b dict -> unit val revapp : (Key.ord_key * 'b -> 'a) -> 'b dict -> unit val fold : (Key.ord_key * 'a * 'b -> 'b) -> 'a dict -> 'b -> 'b val revfold : (Key.ord_key * 'a * 'b -> 'b) -> 'a dict -> 'b -> 'b val map : (Key.ord_key * 'a -> '2b) -> 'a dict -> '2b dict val transform : ('a -> '2b) -> 'a dict -> '2b dict end We note that this definition relies on the signature ORD_KEY which in turn relies on LIB_BASE - we can load these into the interpreter in the appropriate order - given the directory containing the library:

fun uselib f = use ("/usr/local/lib/smllib/"^f);

uselib "lib-base-sig.sml";
uselib "lib-base.sml";
uselib "ord-key-sig.sml";
uselib "dict-sig.sml";

We wish to create a structure which matches the ORD_KEY signature. The ORD_KEY signature is as follows:

signature ORD_KEY =
  sig
    type ord_key
    val cmpKey : ord_key * ord_key -> LibBase.relation
  end

A suitable structure must specify the type ord_key (in this case a string) and supply a function which takes two strings and returns a "LibBase.relation" - it turns out that a "LibBase.relation" is one of the following Equal, Greater and Less. In fact this work has been done in another part of the library but here goes: structure StringKey : ORD_KEY = struct type ord_key = string fun cmpKey(a:string,b:string) = if a=b then LibBase.Equal else if a<b then LibBase.Less else (* a>b *) LibBase.Greater end; The StringKey structure can now be used as a parameter to a functor with signature DICT. We have a choice in the library - there are two implementations: one is based on "Binary search trees of Bounded Balance" the other uses "Splay trees". Not having the vaguest idea of the relative merits of these algorthms (and not wanting to) we toss a coin which requires us to use Binary trees:

uselib "binary-dict.sml";
structure StringDict = BinaryDict(StringKey);

We can now access the StringDict - either by "opening" it or by referencing it directly. We create an empty dictionary - we have to specify the type of the output explicitly:

val empty = StringDict.mkDict() : (int*int) StringDict.dict;

We can add the three items as follows:

 
val dept = StringDict.insert(StringDict.insert(StringDict.insert(
	          empty,"andrew",(236,4677)),
                        "alison",(238,4218)),
                        "gordon",(236,4677));

We can look up the room number and telephone number of an individual in a flash:

StringDict.find(dept,"andrew");