Set

Set module: persistent hash-array-mapped-trie set.

Set(a) is an immutable, hash-indexed collection backed by a HAMT via the Map module (Set(a) ≅ Map(a, Unit) internally). This gives O(log₃₂ n) ≈ O(1) amortized membership tests, insert, and delete.

Operations that need key identity take an explicit comparator: cmp : a -> a -> Bool where cmp(a)(b) = true means a < b

Standard comparators: fn(a) -> fn(b) -> a < b for Int elements fn(a) -> fn(b) -> a < b for String elements (lexicographic)

Iteration order is hash-traversal order (not sorted). Use to_list then sort externally if sorted order is needed.

Types

ptypeSEntrySEntry(a) =#

ptypeSetSet(a) = HamtSet(SEntry(a))#

Functions

fnemptyempty()#

Returns an empty set.

fnsingletonsingleton(x)#

Returns a set containing exactly one element.

fnis_emptyis_empty(s)#

Returns true if the set contains no elements.

fnsizesize(s)#

Returns the number of elements in the set. O(n).

fncontainscontains(s, elem, cmp)#

Returns true if the set contains elem. cmp : a -> a -> Bool where cmp(a)(b) = true means a < b.

fninsertinsert(s, elem, cmp)#

Inserts elem into the set. Returns the set unchanged if elem is already present. cmp : a -> a -> Bool where cmp(a)(b) = true means a < b.

fnremoveremove(s, elem, cmp)#

Removes elem from the set. Returns the set unchanged if elem is absent. cmp : a -> a -> Bool where cmp(a)(b) = true means a < b.

fnunionunion(a, b, cmp)#

Returns the union of two sets (all elements in either set). cmp : a -> a -> Bool where cmp(a)(b) = true means a < b.

fnintersectionintersection(a, b, cmp)#

Returns the intersection of two sets (elements in both sets). cmp : a -> a -> Bool where cmp(a)(b) = true means a < b.

fndifferencedifference(a, b, cmp)#

Returns elements in a that are not in b (set difference a \\ b). cmp : a -> a -> Bool where cmp(a)(b) = true means a < b.

fnis_subsetis_subset(a, b, cmp)#

Returns true if a is a subset of b.

fnto_listto_list(s)#

Returns all elements as a list (hash-traversal order).

fnfrom_listfrom_list(xs, cmp)#

Builds a set from a list of elements. cmp : a -> a -> Bool where cmp(a)(b) = true means a < b.

fnfoldfold(acc, s, f)#

Left fold over all elements. f(acc)(elem) = new_acc.

fneqeq(a, b, cmp)#

Returns true if the two sets contain the same elements. cmp : a -> a -> Bool where cmp(a)(b) = true means a < b.