A Tutorial on Programming Features in ATS:
Prev		Next

Chapter 12. Functional Sets and Maps

Table of Contents
Functional Sets
Functional Maps

Both (finite) sets and (finite) maps are commonly used data structures. Functional sets and maps are immutable after their construction. Insertion into or removal from a functional set/map results in the construction of a new set/map while the original is kept intact. Usually the newly constructed set/map and the original one share a lot of underlying representation. Note that a functional set/map cannot be safely freed explicitly and the memory for representing it can only be reclaimed through garbage collection (GC).

Functional Sets

Suppose that a set is needed for collecting values of type elt_t. The following code essentially sets up an interface for creating and operating on such a set based on a balanced-tree implementation in ATSLIB/libats:

local
//
typedef elt = elt_t
//
staload
FS = "libats/ML/SATS/funset.sats"
implement
$FS.compare_elt_elt<elt>(x, y) = compare(x, y)
//
in (* in-of-local *)

#include "libats/ML/HATS/myfunset.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 sets. Note that it is assumed here that there is a comparison function on values of the type elt_t that overloads the symbol compare. If this is not the case, one needs to implement such a function.

Assume that elt_t is int. The following line of code creates a functional set (of integers) containing no elements:

val myset = myfunset_nil()

The function for inserting an element into a given set is assigned the following type:

//
fun myfunset_insert(xs: &myset >> _, x0: elt): bool
//

The dot-symbol .insert is overloaded with the function myfunset_insert. Note that the first argument of myfunset_insert is call-by-reference. If the given element is inserted into the given set, then the newly created set is stored into the call-by-reference argument and false is returned (to indicate no error). Otherwise, true is returned (to indicate a failure). The following few lines of code shows how insertion can be operated on a functional set:

//
var myset = myset
//
val-false = myset.insert(0) // inserted
val-(true) = myset.insert(0) // not actually inserted
val-false = myset.insert(1) // inserted
val-(true) = myset.insert(1) // not actually inserted
//

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 myfunset_insert. During the course of debugging, one may want to print out the values contained in a given set:

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

where the symbol fprint is overloaded with fprint_myset. The function for removing an element from a given set is assigned the following type:

//
fun myfunset_remove(xs: &myset >> _, x0: elt): bool
//

The dot-symbol .remove is overloaded with the function myfunset_remove. Note that the first argument of myfunset_remove is call-by-reference. If the given element is removed from the given set, then the newly created set is stored into the call-by-reference argument and true is returned. Otherwise, false is returned. The following few lines of code shows how removal can be operated on a functional set:

val-true = myset.remove(0) // removed
val-false = myset.remove(0) // not actually removed
val-true = myset.remove(1) // removed
val-false = myset.remove(1) // not actually removed

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

//
fun myfunset_make_module((*void*)): myset_modtype
//

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

val MYSET = myfunset_make_module()

With MYSET, we can create a (functional) set and then perform certain insertion and removal operations:

//
var myset = (MYSET.nil)()
//
val-false = (MYSET.insert)(myset, 0) // inserted
val-false = (MYSET.insert)(myset, 1) // inserted
//
val ((*void*)) = assertloc((MYSET.size)(myset) = 2)
//
val-(true) = (MYSET.remove)(myset, 0) // removed
//
val ((*void*)) = assertloc((MYSET.size)(myset) = 1)
//
val-(true) = (MYSET.remove)(myset, 1) // removed
//
val ((*void*)) = assertloc((MYSET.size)(myset) = 0)
//

Various common set operations can be found in libats/ML/HATS/myfunset.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.