A Tutorial on Programming Features in ATS:
Prev	Chapter 12. Functional Sets and Maps	Next

Functional Maps

Suppose that a map is needed for mapping keys of type key_t to items of type itm_t. The following code essentially sets up an interface for creating and operating on such a map based on a balanced-tree implementation in ATSLIB/libats:

local
//
typedef
key = key_t and itm = itm_t
//
staload
FM = "libats/ML/SATS/funmap.sats"
implement
$FM.compare_key_key<key>(x, y) = compare(x, y)
//
in (* in-of-local *)

#include "libats/ML/HATS/myfunmap.hats"

end // end of [local]

Please find on-line the HATS file mentioned in the code, which is just a convenience wrapper made to simplify programming with functional maps. Note that it is assumed here that there is a comparison function on values of the type key_t that overloads the symbol compare. If this is not the case, one needs to implement such a function.

Assume that key_t is string and itm_t is int. The following line of code creates an empty functional map:

val mymap = myfunmap_nil()

The following few lines insert some key/item pairs into mymap:

//
var mymap = mymap
//
val-~None_vt() = mymap.insert("a", 0)
val-~Some_vt(0) = mymap.insert("a", 1)
//
val-~None_vt() = mymap.insert("b", 1)
val-~Some_vt(1) = mymap.insert("b", 2)
//
val-~None_vt() = mymap.insert("c", 2)
val-~Some_vt(2) = mymap.insert("c", 3)
//

The dot-symbol .insert is overloaded with a function of the name myfunmap_insert. The first line in the above code may seem puzzling: Its sole purpose is to create a left-value to be passed as the first argument to myfunmap_insert. Given a key and an item, mymap.insert inserts the key/item pair into mymap. If the key is in the domain of the map represented by mymap before insertion, then the original item associated with the key is returned. Otherwise, no item is returned. As can be expected, the size of mymap is 3 at this point:

val () = assertloc (mymap.size() = 3)

The dot-symbol .size is overloaded with a function of the name myfunmap_size, which returns the number of key/item pairs stored in a given map. During the course of debugging, one may want to print out the key/item pairs in a given map:

//
val () = fprintln! (stdout_ref, "mymap = ", mymap)
//

where the symbol fprint is overloaded with fprint_mymap. The next two lines of code show how search with a given key operates on a map:

val-~None_vt() = mymap.search("")
val-~Some_vt(1) = mymap.search("a")

The dot-symbol .search is overloaded with a function of the name myfunmap_search, which returns the item associated with a given key if it is found. The next few lines of code remove some key/item pairs from mymap:

//
val-true = mymap.remove("a")
val-false = mymap.remove("a")
//
val-~Some_vt(2) = mymap.takeout("b")
val-~Some_vt(3) = mymap.takeout("c")
//

The dot-symbol .remove is overloaded with a function of the name myfunmap_remove for removing a key/item pair of a given key. If a key/item pair is removed, then the function returns true. Otherwise, it returns false to indicates that no key/item pair of the given key is stored in the map being operated on. The dot-symbol .takeout is overloaded with a function of the name myfunmap_takeout, which is similar to myfunmap_remove excepting for returning the removed item.

The following function is available for generating a module (that is, a record) containing various operations on mymap-values:

//
fun myfunmap_make_module((*void*)): mymap_modtype
//

For instance, a module of the name MYMAP is created as follows:

val MYMAP = myfunmap_make_module()

With MYMAP, we can create a (functional) map and then perform various insertion and removal operations:

//
var mymap = (MYMAP.nil)()
//
val-~None_vt() = (MYMAP.insert)(mymap, "a", 0)
val-~None_vt() = (MYMAP.insert)(mymap, "b", 1)
val-~None_vt() = (MYMAP.insert)(mymap, "c", 2)
//
val-~Some_vt(0) = (MYMAP.insert)(mymap, "a", 1)
val-~Some_vt(1) = (MYMAP.insert)(mymap, "b", 2)
val-~Some_vt(2) = (MYMAP.insert)(mymap, "c", 3)
//
val-(true) = (MYMAP.remove)(mymap, "a")
val-(true) = (MYMAP.remove)(mymap, "b")
val-(true) = (MYMAP.remove)(mymap, "c")
//
val () = assertloc((MYMAP.size)(mymap) = 0)
//

Various common map operations can be found in libats/ML/HATS/myfunmap.hats. By following the types assigned to these operations, one should have no difficulty in figuring out how they are supposed to be called. Please find the entirety of the code used in this section on-line.