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 ab *) 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");