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).
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]
Assume that elt_t is int. The following line of code creates a functional set (of integers) containing no elements:
The function for inserting an element into a given set is assigned the following type: 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 //
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:
For instance, a module of the name MYSET is created as follows: 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.