tur/set
typed Set[A]: persistent set backed by the HAMT.
A must satisfy Hash[A] and Eq[A]. Elements are stored as HAMT keys.
Since: Phase TC2-C
Set
(defstruct Set :heap [A] (hamt :ptr<void>))
parameterized persistent set with element type A.
Since: Phase TC2
set-new
(set-new [A])
create a new empty Set[A].
An empty Set[A].
(set-new) ; => empty Set
Since: Phase TC2
set-add-eq-o
(set-add-eq-o [A])
============================================================================ Raw carrier layer (mirrors map-assoc-eq-o et al.).
These carry the element already boxed into the int64 carrier (a :int, not :A) plus an explicit comparator (from MapKey[A].mk-cmp) and ownership flag (from MapKey[A].mk-owned?), delegating to the ownership-aware HAMT ops. They are the thin C layer the public Hash/MapKey-dispatched set-add / set-remove / set-member? below delegate to. The value slot is always the sentinel (void*)1 (a Set is a Map to unit). Element content-equality is resolved by keyeq when two elements share a hash, so distinct pointers with equal content (e.g. two "hi" strings) are one member; the comparator is stamped on the resulting HAMT root so structural Eq[Set] recovers it. ============================================================================ set-add-eq-o -- raw insert: explicit hash, boxed carrier element, comparator and ownership flag.
set-has-eq-o?
(set-has-eq-o? [A])
raw membership test: explicit hash, boxed carrier element.
set-del-eq-o
(set-del-eq-o [A])
raw removal: explicit hash, boxed carrier element.
set-add
(set-add [s h x])
add element x to the set; returns a new set.
| s | Set[A] | |
| h | precomputed hash of x (from Hash[A] typeclass) | |
| x | element to add (type A) |
A new Set[A] containing x.
(set-add my-set (hash 42) 42) ; => set with 42
Since: Phase TC2 (element retyped :int -> :A, content-keyed: set-element-api-generalization)
set-remove
(set-remove [s h x])
remove element x from the set; returns a new set.
| s | Set[A] | |
| h | precomputed hash of x | |
| x | element to remove (type A) |
A new Set[A] without x.
(set-remove my-set (hash 42) 42) ; => set without 42
Since: Phase TC2
set-member?
(set-member? [s h x])
check whether element x is in the set.
| s | Set[A] | |
| h | precomputed hash of x | |
| x | element to test (type A) |
true if x is in the set, false otherwise.
(set-member? my-set (hash 42) 42) ; => true
Since: Phase TC2
set-count
(set-count [A])
return the number of elements in the set.
| s | Set[A] |
Integer count of elements.
(set-count my-set) ; => 3
Since: Phase TC2
set-union
(set-union [A])
compute the union of two sets.
| a | first Set[A] | |
| b | second Set[A] |
A new Set[A] containing all elements from both sets.
(set-union set-a set-b) ; => union set
Since: Phase TC2
set-intersect
(set-intersect [A])
compute the intersection of two sets.
| a | first Set[A] | |
| b | second Set[A] |
A new Set[A] containing only elements present in both a and b.
(set-intersect set-a set-b) ; => intersection set
Since: Phase TC2
set-diff
(set-diff [A])
compute set difference a \ b (elements in a but not b).
| a | Set[A] (base set) | |
| b | Set[A] (elements to remove) |
A new Set[A] with elements of a that are not in b.
(set-diff set-a set-b) ; => difference set
Since: Phase TC2
set-eq?
(set-eq? [a :int b :int])
compare two sets for equality.
| a | first Set[A] | |
| b | second Set[A] |
true if both sets contain exactly the same elements.
(set-eq? set-a set-b) ; => true
Since: Phase TC2
set-eq-cmp?
(set-eq-cmp? [A])
structural equality with a user-supplied element comparator. Use this variant when the element type is not primitive (e.g. Set[Vec[int]]) because the hash-based set-eq? compares elements by hash + pointer equality, which is wrong for structurally-equal-but-distinctly-allocated values.
| a | Set[A] | |
| b | Set[A] | |
| cmp-fn | comparator fn [a :int b :int] :bool applied to element pairs |
true iff both sets have the same count and every element of a
has at least one structurally-equal counterpart in b per cmp-fn.
Since: Phase F3-5 (cross-plan-followups)
set-free
(set-free [A])
free the Set wrapper struct.
| s | Set[A] to free |
(set-free my-set)
Since: Phase TC2
set-hamt
(set-hamt [A])
internal accessor returning the backing HAMT pointer.
set-eq-loop
(set-eq-loop [iter :ptr<void> s2-hamt :ptr<void> keyeq :ptr<void>] :bool)
pure-Turmeric structural-equality walk over s1's HAMT.
Path A specializes this per A at the Eq [Set] dispatch site; the self-tail-recursive spec lowers to a goto loop (TCO-in-ABI-specs, same gate as vec-eq-loop / mutmap-eq-loop), so deep iteration over large sets runs in constant stack. For each entry of s1 the matching key is looked up in s2's hamt via hamt/has-dynamic? (threading s1's stamped key comparator so content-keyed elements stay content-correct).
| iter | hamt/iter-alloc-allocated handle scanning s1 | |
| s2-hamt | raw HAMT pointer of the second set (from set-hamt) | |
| keyeq | stamped key comparator (from hamt/keyeq on s1's hamt) |
true iff every entry of s1 is present in s2 under keyeq.
Since: Phase TCO-Eq-MapSet
set-eq-driver
(set-eq-driver [A])
allocate the iter box, run set-eq-loop, free.
Since: Phase TCO-Eq-MapSet
set-eq-full
(set-eq-full [A])
membership equality using the HAMT structure. set-eq-full -- length-prefixed structural equality over by-value (Set A).
Pulled out as a single-receiver helper so the Eq [Set] instance reads x and y exactly once each, mirroring the original single-use instance shape. Takes by-value (Set A) (Path A), so a concrete (Set int) receiver dispatches via the typed per-A spec set_eq_full__spec__bool_Set__int___Set__int__(Set__int *, Set__int *) instead of the int64 carrier -- giving Eq [Set] a typed (Set__A *) consumer, matching Eq [Map] / Eq [MutableMap] / Eq [Vec]. An HKT-headed (abstract-A) receiver still instantiates the int64 carrier (set_hyeq_hyfull), so existing carrier callers are unaffected.
Eq[Set]
(definstance Eq [Set])
set-add-elem__
(set-add-elem__ [^Hash A ^MapKey A])
internal: typed single-element insert behind set-add1.
set-of-element-type-is-not-checked: set-of used to have no homogeneity check -- set-add1 expanded straight to the carrier-typed set-add-eq-o, each element resolving its own Hash/MapKey, so (set-of 1 "two") built and claimed (Set int) while holding a cstr. Routing every insert through this TYPED helper is the vec-push! shape: the element must be the set's A, and a mismatch is a TUR-E0001 at the offending element. A heterogeneous set is spelled (Set any) -- Hash[any]/MapKey[any] satisfy the constraints and each any keys by its payload -- which is what a Saffron #set{...} literal widens to.
set-add1
(set-add1 [s x])
insert one element, computing its hash via Hash[A].
The convenient single-element add: the element expression is mentioned exactly once (it becomes the argument of the typed set-add-elem__, which hashes and boxes it), so the set-of / #set{...} lowering evaluates a computed element once. The element must have the set's element type; content-keyed via Hash[A] + MapKey[A], so (set-of "a" "a") -- two equal strings -- is one member even at distinct addresses.
| s | the set | |
| x | the element to insert |
A new set containing x.
(set-add1 (set-new) 42) ; => Set {42}
set-add-each__
(set-add-each__ [^syntax s & ^syntax xs])
internal helper for the set-of macro.
Threads (set-add1 s x) over the elements in xs. Each element appears once in the expansion (set-add1 supplies the duplicate hash slot), so a computed element is evaluated exactly once. Recursive: each step nests one more set-add1. Its parameters and set-of's are ^syntax, for the reason hamt-assoc-each__ gives (map.tur): an element holding a lambda.
set-empty-for
(set-empty-for [^Hash A ^MapKey A])
variadic Set literal.
| & xs -- zero or more elements of a single type A. Each element is used | ||
| as its own hash (identity-hash), matching the typed Set[A] | ||
| convention; scalar element types (int, etc.) dedupe by value. |
A fresh Set[A] containing xs; duplicate elements collapse to one.
(set-of) ; => empty Set
(set-of 1 2 3) ; => Set {1, 2, 3}
(set-of 1 1 2) ; => Set {1, 2}
Note: this is the lowering target of the #set{...} data literal
(-Xdata-literals). Writing #set{1 2 3} is preferred over calling
set-of directly.
set-empty-for -- internal: an empty Set[A] whose A is pinned by a sample element. Used by the set-of / #set{...} lowering, where the element type is known from the first literal element but cannot be written as an annotation by the expanding macro. The x argument is consumed only for type inference; the returned set is empty. Mirrors map-empty-for. Without this, set-of seeds from a bare (set-new) whose A is unpinned, so the per-element MapKey dispatch defaults to the int carrier and content-keyed elements (cstr, ...) are not deduped.
Since: set-element-api-generalization
set-of
(set-of [& ^syntax xs])