Set[T] is a hash set: an unordered collection in which each value appears at
most once. Membership, insertion, and removal are average constant time.
fn main(): void {
mut tags: Set[string] = Set.new()
tags.add("stable")
tags.add("documented")
tags.add("stable") // already present — no second member
println("${tags.size()} tags")
println("stable? ${tags.contains("stable")}")
}As with Map, the binding must be mut (because add takes mut self) and
the annotation is what fixes the element type for Set.new().
Construction
Set.new(capacity) allocates an empty set; the capacity is only an allocation
hint. Set.copy(other, capacity) gives independent storage.
fn main(): void {
// Element type from the annotation.
mut a: Set[int] = Set.new()
a.add(1)
// Element type from an explicit type argument, with a capacity hint.
mut b := Set.new[int](128)
b.add(2)
// Independent table — adding to `c` leaves `a` alone.
mut c := Set.copy(a)
c.add(3)
println("${a.size()} ${b.size()} ${c.size()}")
}List.to_set() is the shortest way to build a set from known values, and
doubles as a deduplicator:
fn main(): void {
words := ["fig", "date", "fig", "kiwi", "date"]
unique := words.to_set()
println("${words.len()} values, ${unique.size()} distinct")
// Sorted, so the output is deterministic.
for word in unique.to_list().sorted() {
println(word)
}
}Set[T] is a handle to heap storage. Passing it or binding it to another name
shares the same table; Set.copy is what isolates later mutation.
fn marked_count(target: Set[string]): int {
mut local := Set.copy(target)
local.add("marker")
return local.size()
}
fn main(): void {
mut tags: Set[string] = Set.new()
tags.add("stable")
copied := marked_count(tags)
println("copy has ${copied}")
println("original still has ${tags.size()}")
}Membership and mutation
add returns nothing; remove returns a bool saying whether the value was
present.
fn main(): void {
mut roles: Set[string] = Set.new()
roles.add("admin")
roles.add("auditor")
println("${roles.contains("admin")}")
println("${roles.is_empty()} ${roles.is_not_empty()}")
println("${roles.size()} ${roles.len()}") // len() is an alias for size()
if roles.remove("auditor") {
println("auditor revoked")
}
if !roles.remove("auditor") {
println("already gone")
}
roles.clear()
println("${roles.size()}")
}add is a statement, not an expression — it does not report whether the value
was new. Test with contains first when you need to know:
fn main(): void {
mut roles: Set[string] = Set.new()
inserted: bool = roles.add("admin")
println("${inserted}")
}Relationships
Four predicates answer containment questions without allocating.
fn main(): void {
mut granted: Set[string] = Set.new()
granted.add("read")
granted.add("write")
granted.add("admin")
mut required: Set[string] = Set.new()
required.add("read")
required.add("write")
println("${granted.contains_all(required)}") // every required is granted
println("${required.is_subset_of(granted)}") // same question, other way round
println("${granted.is_superset_of(required)}") // and again
println("${granted.is_disjoint(required)}") // no member in common?
}| Call | Question |
|---|---|
left.contains_all(right) |
Does left hold every member of right? |
left.is_subset_of(right) |
Is every member of left in right? |
left.is_superset_of(right) |
Is every member of right in left? |
left.is_disjoint(right) |
Do the two share no members? |
Algebra
The four algebra operations each allocate a new set and leave both operands untouched.
fn main(): void {
mut left: Set[int] = Set.new()
left.add(1)
left.add(2)
left.add(3)
mut right: Set[int] = Set.new()
right.add(3)
right.add(4)
either := left.union(right) // 1 2 3 4
both := left.intersect(right) // 3
only_left := left.subtract(right) // 1 2
one_side := left.symmetric_difference(right) // 1 2 4
println("${either.size()} ${both.size()} ${only_left.size()} ${one_side.size()}")
println("operands unchanged: ${left.size()} ${right.size()}")
}plus, plus_all, and minus are the single-value counterparts, also
non-mutating:
fn main(): void {
mut base: Set[string] = Set.new()
base.add("a")
mut extra: Set[string] = Set.new()
extra.add("b")
extra.add("c")
println("${base.plus("z").size()}") // 2
println("${base.plus_all(extra).size()}") // 3
println("${base.minus("a").size()}") // 0
println("${base.size()}") // still 1
}A permission check reads naturally with the algebra operators — compute what is missing rather than looping:
fn missing_permissions(granted: Set[string], required: Set[string]): []string {
return required.subtract(granted).to_list().sorted()
}
fn main(): void {
mut granted: Set[string] = Set.new()
granted.add("read")
mut required: Set[string] = Set.new()
required.add("read")
required.add("write")
required.add("delete")
missing := missing_permissions(granted, required)
if missing.is_empty() {
println("authorised")
} else {
for name in missing {
println("missing: ${name}")
}
}
}Iteration
for value in set walks the members. Order is a property of the hash table and
is not specified — sort before presenting anything.
fn main(): void {
mut tags: Set[string] = Set.new()
tags.add("runtime")
tags.add("memory")
tags.add("types")
// Fine: order does not affect the result.
mut total := 0
for tag in tags {
total = total + tag.len()
}
println("${total}")
// Presentation: sort first.
for tag in tags.to_list().sorted() {
println("- ${tag}")
}
}for_each_item takes a callback, and try_for_each_item stops as soon as the
callback returns false:
fn main(): void {
mut ids: Set[int] = Set.new()
ids.add(1)
ids.add(2)
ids.for_each_item(id => println("id ${id}"))
all_positive := ids.try_for_each_item(id => id > 0)
println("${all_positive}")
}A set has no positions and no keyed retrieval — contains is the only lookup.
There is no get:
fn main(): void {
mut ids: Set[int] = Set.new()
ids.add(1)
println("${ids.get(0) ?? 0}")
}When you need to retrieve a stored value rather than merely test for it, you
want a Map keyed by the identifying part.
Transformation
map and flat_map return sets, so they can shrink: several inputs mapping to
one output collapse to a single member.
fn main(): void {
mut tags: Set[string] = Set.new()
tags.add("Runtime")
tags.add("RUNTIME")
tags.add("Memory")
normalized := tags.map(tag => tag.to_lower_ascii())
println("${tags.size()} in, ${normalized.size()} out") // 3 in, 2 out
public_tags := normalized.filter(tag => !tag.starts_with("_"))
println("${public_tags.size()}")
}flat_map has a signature worth reading twice: its callback returns a
Set[R], not a []R. That is the opposite of List.flat_map and of
Map.flat_map, both of which take a list-returning callback.
fn digits_of(n: int): Set[int] {
mut out: Set[int] = Set.new()
mut v := n
if v == 0 { out.add(0) }
for v > 0 {
out.add(v % 10)
v = v / 10
}
return out
}
fn main(): void {
mut numbers: Set[int] = Set.new()
numbers.add(121)
numbers.add(35)
digits := numbers.flat_map(n => digits_of(n))
for d in digits.to_list().sorted() { println("${d}") }
}Returning a list from that callback is a type error:
fn main(): void {
mut numbers: Set[int] = Set.new()
numbers.add(3)
pairs := numbers.flat_map(n => [n, n + 1])
println("${pairs.size()}")
}Predicates and searches mirror the Map surface:
fn main(): void {
mut sizes: Set[int] = Set.new()
sizes.add(1)
sizes.add(8)
sizes.add(64)
println("${sizes.any(n => n > 32)}") // short-circuits
println("${sizes.all(n => n > 0)}") // short-circuits
println("${sizes.none(n => n < 0)}") // short-circuits
println("${sizes.count(n => n > 4)}") // visits every member
match sizes.find(n => n > 4) {
Some(n) => println("found ${n}")
None => println("none above 4")
}
}find returns an arbitrary match under hash order. When several members
qualify and you care which one you get, sort a list instead:
fn main(): void {
mut sizes: Set[int] = Set.new()
sizes.add(64)
sizes.add(8)
sizes.add(16)
// Deterministic: the smallest member above 4.
first_big := sizes.to_list().sorted().find(n => n > 4)
println("${first_big ?? 0}")
}Members
A member type needs Equatable and Hashable. @derive generates both from
the fields:
@derive(Equatable, Hashable)
struct Version { major: int, minor: int }
fn main(): void {
mut seen: Set[Version] = Set.new()
seen.add(Version { major: 1, minor: 0 })
seen.add(Version { major: 1, minor: 0 }) // structurally equal — no growth
seen.add(Version { major: 1, minor: 1 })
println("${seen.size()}")
println("${seen.contains(Version { major: 1, minor: 1 })}")
}Hand-written impls let the identity ignore part of the value — here two records are the same member when their ids match, regardless of the label:
struct Node { id: int, label: string }
impl Equatable for Node {
fn equals(self, other: Node): bool { return self.id == other.id }
}
impl Hashable for Node {
fn hash_code(self): int { return self.id }
}
fn main(): void {
mut nodes: Set[Node] = Set.new()
nodes.add(Node { id: 7, label: "first" })
nodes.add(Node { id: 7, label: "second" })
println("${nodes.size()}") // 1
println("${nodes.contains(Node { id: 7, label: "any" })}") // true
}Equal values must hash equal, and a stored member’s participating fields must
not change while it is in the set — a mutated member stays in its old bucket
and becomes unreachable by contains.
Generic helpers
A Hashable bound is all a function needs to build or query sets over any
member type:
fn set_of[T: Hashable](items: []T): Set[T] {
mut out: Set[T] = Set.new()
for item in items { out.add(item) }
return out
}
fn shared[T: Hashable](left: []T, right: []T): Set[T] {
return set_of(left).intersect(set_of(right))
}
fn main(): void {
common := shared([1, 2, 3, 4], [3, 4, 5])
println("${common.size()}")
println("${shared(["a", "b"], ["b", "c"]).size()}")
}Sorted sets are declaration-only
The prelude declares SortedSet[T] — boundary queries (first, last),
ranges (head_set, tail_set, sub_set), and nearest-value lookup (floor,
ceiling) — plus Set.to_sorted_set() to build one. Every one of those
methods is a bodyless declaration. Nothing constructs a SortedSet and
nothing can run against one; a program that mentions it type-checks and then
fails to build:
fn main(): void {
mut ports: Set[int] = Set.new()
ports.add(443)
ports.add(22)
// Type-checks, then fails to lower:
// ATOLL2004: builtin method `to_sorted_set` has no lowering path
sorted := ports.to_sorted_set()
println("lowest ${sorted.first() ?? 0}")
}Ordered access today means sorting a list of the members. Boundary and nearest-value questions are then a scan over that list:
fn main(): void {
mut ports: Set[int] = Set.new()
ports.add(443)
ports.add(22)
ports.add(80)
ordered := ports.to_list().sorted()
println("lowest ${ordered.first() ?? 0}, highest ${ordered.last() ?? 0}")
// "At or below 100" — the largest member that is <= 100.
mut floor := 0
for p in ordered {
if p <= 100 { floor = p }
}
println("at or below 100: ${floor}")
below_443 := ordered.filter(p => p < 443)
println("${below_443.len()} below 443")
}Equality and hashing of sets
Set equality is membership-based, not insertion-order-based, and the hash folds members commutatively so equivalent sets stay interchangeable as fields of derived hashable values.
fn main(): void {
mut left: Set[string] = Set.new()
left.add("a")
left.add("b")
mut right: Set[string] = Set.new()
right.add("b")
right.add("a")
right.add("a") // duplicate — changes nothing
println("${left.size() == right.size()}")
println("${left.hash_code() == right.hash_code()}")
}A worked example
Diffing two configuration snapshots: what was added, what was removed, and what stayed — using nothing but set algebra, with sorted output.
struct Snapshot { name: string, features: Set[string] }
fn snapshot(name: string, features: []string): Snapshot {
return Snapshot { name: name, features: features.to_set() }
}
fn diff(before: Snapshot, after: Snapshot): void {
added := after.features.subtract(before.features)
removed := before.features.subtract(after.features)
kept := before.features.intersect(after.features)
churn := before.features.symmetric_difference(after.features)
println("${before.name} -> ${after.name}")
for feature in added.to_list().sorted() { println(" + ${feature}") }
for feature in removed.to_list().sorted() { println(" - ${feature}") }
println(" ${kept.size()} unchanged, ${churn.size()} changed")
if churn.is_empty() {
println(" identical")
}
}
fn main(): void {
v1 := snapshot("v1", ["tracing", "metrics", "legacy_auth"])
v2 := snapshot("v2", ["tracing", "metrics", "oauth"])
diff(v1, v2)
diff(v2, v2)
}