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:
// 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:
// 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.