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, replacing any present element ==-equal to x.

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

_EncodedElement

struct _EncodedElement<T>
  key: bytes
  value: T
end

impl<T> Ord<_EncodedElement<T>>

cmp

def cmp(self, other: Self) -> Ordering

Orders by the element's encoded bytes.

@no-doctest: internal ordering helper for canonical Set encoding

encodedelement!

def _encoded_element!<T: Encode>(x: T) -> _EncodedElement<T>

encodedelements!

def _encoded_elements!<T: Encode>(xs: List<T>) -> List<_EncodedElement<T>>

emitelements!

def _emit_elements!<T: Encode, S: Serializer>(sorted: List<_EncodedElement<T>>, s: S) -> ()

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

encode!

def encode!<S: Serializer>(self, s: S) -> ()

Writes the elements as a sequence ordered by their encoded bytes.

a = Set.from_list(List.empty().append(1i32).append(2i32))
b = Set.from_list(List.empty().append(2i32).append(1i32))
codec.to_bytes(a) == codec.to_bytes(b) => true

setdecode!

def _set_decode!<T: Hash + Decode, D: Deserializer>(d: D, remaining: int, acc: Set<T>, depth: int) -> Result<Set<T>, DecodeError>

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

decode!

def decode!<D: Deserializer>(d: D, depth: int) -> Result<Set<T>, DecodeError>

Reads a sequence of elements back into a set.

@no-doctest: see the trait method in core/decode; the tests below round-trip through it