Comparison of programming languages (associative array): Difference between revisions

Revision as of 07:23, 5 June 2009

Revision as of 07:47, 26 June 2009

Line 981:

The SML'97 standard of the [[Standard ML]] programming language does not provide any associative containers. However, various implementations of Standard ML do provide associative containers.

The library of the popular [[Standard ML of New Jersey]] implementation provides a signature (kind of like an "interface"), <code>ORD_MAP</code>, which defines a common interface for ordered functional (immutable) associative arrays. There are threeseveral general functors, <code>BinaryMapFn</code>, <code>ListMapFn</code>, <code>RedBlackMapFn</code>, and <code>SplayMapFn</code>, that allow you to create the corresponding type of ordered map (the types are a [[self-balancing binary search tree]], sorted [[association list]], [[red-black tree]], and [[splay tree]], respectively) using a user-provided structure to describe the key type and comparator. The functor returns a structure that follows the <code>ORD_MAP</code> interface. In addition, there are two pre-defined modules for associative arrays with integer keys: <code>IntBinaryMap</code> and <code>IntListMap</code>.

<pre>

Line 1,002:

val it = SOME "555-1212" : string option

</pre>

SML/NJ also provides a polymorphic hash table:

<source lang="sml">

- exception NotFound;

exception NotFound

- val m : (string, string) HashTable.hash_table = HashTable.mkTable (HashString.hashString, op=) (3, NotFound);

val m =

HT

{eq_pred=fn,hash_fn=fn,n_items=ref 0,not_found=NotFound(-),

table=ref [|NIL,NIL,NIL,NIL,NIL,NIL,NIL,NIL,NIL,NIL,NIL,NIL,...|]}

: (string,string) HashTable.hash_table

- HashTable.insert m ("Sally Smart", "555-9999");

val it = () : unit

- HashTable.insert m ("John Doe", "555-1212");

val it = () : unit

- HashTable.insert m ("J. Random Hacker", "553-1337");

val it = () : unit

HashTable.find m "John Doe"; (* returns NONE if not found *)

val it = SOME "555-1212" : string option

- HashTable.lookup m "John Doe"; (* raises the exception if not found *)

val it = "555-1212" : string

</source>

Monomorphic hash tables are also supported using the <code>HashTableFn</code> functor.

Another Standard ML implementation, [[Moscow ML]], also provides some associative containers. First, it provides polymorphic hash tables in the <code>Polyhash</code> structure. Also, some functional maps from the SML/NJ library above are available as <code>Binarymap</code>, <code>Splaymap</code>, and <code>Intmap</code> structures.