set

stdlib/core/set.hk: Set<T>, a persistent set as a thin keys-only layer over the core Map HAMT.

Representation: Set<T> wraps Map<T, ()>. An element is a key whose value is unit, and membership, insertion and removal therefore reuse the tested HAMT and inherit its persistence (structural sharing) and O(log16 n) operations. Iteration order (to_list, Display) is hash order, unspecified and unstable, and never insertion order, as for the underlying Map.

Elements are bounded by Hash, whose Eq supertrait leaves == working; an element type must therefore be hashable. Eq/Hash/Display for the set itself are hand-written and not derived, the value type being unit and the set's identity is its element membership, order-independent: two sets are equal iff they hold the same elements, and hash accordingly.

The struct is opaque: the representation is private and can change without breaking callers.

Set

opaque Set<T>
  inner: Map<T, ()>
end

impl<T: Hash> Set<T>

empty

def empty() -> Set<T>

The empty set. The element type is fixed by the binding it flows into or by the first insert.

s: Set<i32> = Set.empty()
s.length => 0

from_list

def from_list(items: List<T>) -> Set<T>

A set of every element in items; duplicates collapse.

s = Set.from_list(List.empty().append(1i32).append(2i32).append(1i32))
s.length => 2

insert

def insert(self, x: T) -> Set<T>

self with x added; a no-op if x is already present.

Set.empty().insert(1i32).contains?(1i32) => true

contains?

def contains?(self, x: T) -> bool

Whether x is a member.

Set.empty().insert(1i32).contains?(2i32) => false

remove

def remove(self, x: T) -> Set<T>

self with x removed; a no-op if x is absent.

Set.empty().insert(1i32).remove(1i32).empty? => true

length

prop length(self) -> int

The number of elements.

Set.empty().insert(1i32).insert(2i32).length => 2

empty?

prop empty?(self) -> bool

Whether the set has no elements.

Set.empty().empty? => true

to_list

def to_list(self) -> List<T>

The elements as a list, in the underlying hash order.

Set.empty().insert(1i32).to_list().length => 1

union

def union(self, other: Set<T>) -> Set<T>

Every element in either set.

a = Set.empty().insert(1i32)
a.union(Set.empty().insert(2i32)).length => 2

intersection

def intersection(self, other: Set<T>) -> Set<T>

The elements in both sets.

a = Set.empty().insert(1i32).insert(2i32)
a.intersection(Set.empty().insert(2i32).insert(3i32)).length => 1

difference

def difference(self, other: Set<T>) -> Set<T>

The elements in self but not other.

a = Set.empty().insert(1i32).insert(2i32)
a.difference(Set.empty().insert(2i32)).length => 1

impl<T: Hash> Eq<Set<T>>

eq?

def eq?(self, other: Self) -> bool

Equal where both sets have the same elements.

Set.from_list(List.empty().append(1i32).append(2i32)) == Set.from_list(List.empty().append(2i32).append(1i32)) => true

impl<T: Hash> Hash<Set<T>>

hash

prop hash(self) -> u64

Hashes the value, which lets Set<T> key a Map or Set.

Set.from_list(List.empty().append(1i32).append(2i32)).hash == Set.from_list(List.empty().append(2i32).append(1i32)).hash => true

renderelems

def _render_elems<T: Display>(xs: List<T>) -> string

impl<T: Hash + Display> Display<Set<T>>

to_string

def to_string(self) -> string

Renders the set as {item, …} in element order.

@no-doctest: hash-order rendering is unspecified