(std hashset)

Reference

Overview

Persistent unordered hash set backed by a CHAMP prefix tree, with builder and transient.

(import (std hashset))

(def s (list->hashset (list 1 2 3)))
(hashset-contains? s 2)                    ; #t
(hashset-length (hashset-add s 2))         ; 3, already present
(hashset-length (hashset-add s 4))         ; 4
(hashset-length s)                         ; 3, s is unchanged
(hashset-union s (list->hashset (list 3 4)))   ; #{1 2 3 4}, unordered

(HashSet a) is an immutable, persistent hash set. Updates return a new set sharing untouched subtrees with the original. Implemented as a CHAMP trie (Compressed Hash-Array Mapped Prefix-tree, runtime class Set.Set), serving as the set counterpart to the prelude’s persistent Map.

Element equality. Constructors (hashset-empty, seq->hashset, list->hashset, vec->hashset, hashsetbuilder-empty, transienthashset-empty, and the hash-setting collector) require an Eq instance for the element type, using it for equality and hashing. Derived sets retain the key comparer of the source set.

Unordered. Hash sets are unordered; iteration order is not guaranteed. For sorted set operations, use (std orderedset).

Batch mutations and construction. A HashSetBuilder collects elements into a flat buffer and constructs the trie in a single pass. A TransientHashSet modifies trie nodes in place and converts to a persistent set in O(1) time. Both outperform repeated calls to hashset-add for bulk updates.

Traits. Implements Iterable, Collection, Refable (where (ref s x) tests membership), Addable, Eq, Written and Displayed. Two sets are = if they contain identical elements. Builders and transients implement Addable!, and transients implement Refable.

See also: HashSet, hashset-empty, hashset-add, hashset-contains?, hashset-union, HashSetBuilder, TransientHashSet

Reference

Types

Functions

Types

HashSet

type alias ↑ Types

Persistent, unordered hash set.

%a
The element type. Requires an Eq instance.
(def s (hashset-add (hashset-empty) "a"))
(hashset-contains? s "a")   ; #t
(ref s "b")                 ; #f

See also: hashset-empty, hashset-add, hashset-contains?, HashSetBuilder, TransientHashSet, HashSetting

HashSetBuilder

type alias ↑ Types

Mutable buffer for constructing a persistent hash set in a single pass.

%a
The element type.
(def b (hashsetbuilder-empty))
(hashsetbuilder-add! b 1)
(hashsetbuilder-add! b 1)
(hashsetbuilder-length b)     ; 2
(hashsetbuilder->hashset b)   ; #{1}

Appends elements to a flat array buffer. Calling hashsetbuilder->hashset constructs the CHAMP trie in a single pass, avoiding intermediate trie allocations. Builders do not support lookups or removals; use TransientHashSet for mutable set operations. Implements Addable!.

See also: hashsetbuilder-empty, hashsetbuilder-add!, hashsetbuilder->hashset, TransientHashSet

TransientHashSet

type alias ↑ Types

Mutable transient hash set for batch in-place updates.

%a
The element type.
(def t (hashset->transienthashset s))
(transienthashset-add! t 4)
(transienthashset-remove! t 1)
(transienthashset->hashset t)

Provides in-place mutators mirroring persistent hashset- functions. Mutates owned trie nodes in place without copying. Calling transienthashset->hashset yields a persistent set in O(1) time. The transient remains usable afterward; subsequent writes perform copy-on-write on shared nodes. Implements Addable! and Refable.

See also: hashset->transienthashset, transienthashset->hashset, transienthashset-add!, HashSetBuilder

HashSetCursor

type alias ↑ Types

Cursor for iterating over a persistent hash set.

%a
The element type.

Used by the Iterable implementation of HashSet for loop and for-each iteration. Immutable cursor value: advancing produces a new cursor without mutating the previous one.

See also: HashSet

HashSetting

union ↑ Types

Collector for accumulating elements into a hash set via loop.

%a
The element type. Requires an Eq instance.
hash-setting
The collector constructor.
(loop (:for x (range 0 10))
      (:when (= 0 (% x 2)))
      (:acc s (hash-setting x)))   ; #{0 2 4 6 8}, unordered

Collects elements into a HashSetBuilder.

See also: list->hashset, HashSetBuilder

Functions

hashset-empty

function ↑ Functions

(: hashset-empty (-> (HashSet %a)))
(hashset-empty)

Creates an empty persistent hash set.

returns
An empty hash set using the element type's Eq instance.

See also: hashset-clear, seq->hashset, list->hashset

hashset-add

function ↑ Functions

(: hashset-add (-> (HashSet %a) %a (HashSet %a)))

Returns a new set with an element added.

s
The source set (unmodified).
x
The element to add.
returns
A new set containing x. If x is already present, returns an equivalent set.

See also: hashset-add-all, hashset-remove, add

hashset-add-all

function ↑ Functions

(: hashset-add-all (-> (HashSet %a) (Seq %a) (HashSet %a)))

Returns a new set with all elements of a sequence added.

s
The source set (unmodified).
xs
Sequence of elements to add.
returns
A new set containing all elements from s and xs.

Executes through a transient, copying the trie once rather than once per element.

See also: hashset-add, hashset-union, transienthashset-add-all!

hashset-remove

function ↑ Functions

(: hashset-remove (-> (HashSet %a) %a (HashSet %a)))

Returns a new set with an element removed.

s
The source set (unmodified).
x
The element to remove.
returns
A new set without x. If x was absent, returns s directly.

See also: hashset-remove-all, hashset-filter

hashset-remove-all

function ↑ Functions

(: hashset-remove-all (-> (HashSet %a) (Seq %a) (HashSet %a)))

Returns a new set with all elements of a sequence removed.

s
The source set (unmodified).
xs
Sequence of elements to remove.
returns
A new set excluding elements in xs.

Executes through a transient, copying the trie once rather than once per element.

See also: hashset-remove, transienthashset-remove-all!

hashset-contains?

function ↑ Functions

(: hashset-contains? (-> (HashSet %a) %a bool))

Tests if an element is in the set.

s
The set to inspect.
x
The element to locate.
returns
#t if x is present, otherwise #f.

See also: ref, hashset-find

hashset-length

function ↑ Functions

(: hashset-length (-> (HashSet %a) int))

Returns the number of elements in the set.

s
The set.
returns
The count of elements.

See also: hashset-empty?, length

hashset-empty?

function ↑ Functions

(: hashset-empty? (-> (HashSet %a) bool))

Tests if the set contains no elements.

s
The set.
returns
#t if empty, otherwise #f.

See also: hashset-length, empty?

hashset-clear

function ↑ Functions

(: hashset-clear (-> (HashSet %a) (HashSet %a)))

Returns an empty set retaining the key comparer of the source set.

s
The set whose comparer is preserved.
returns
An empty persistent set.

See also: hashset-empty, hashset-remove-all

hashset-union

function ↑ Functions

(: hashset-union (-> (HashSet %a) (HashSet %a) (HashSet %a)))

Returns the union of two sets.

s
The first set.
other
The second set.
returns
A new set containing elements from both sets.

The resulting set retains the equality comparer of s. If elements are equal, the element from s is retained. When both sets share identical comparers and ancestral subtrees, untouched branches are shared directly without per-element traversal.

See also: hashset-add-all

hashset-map

function ↑ Functions

(: hashset-map (-> (-?-> %a %b) (HashSet %a) (HashSet %b)))
(hashset-map f s)

Transforms all elements using a function, returning a new set.

f
Transformation function applied to each element.
s
The source set.
returns
A new set of transformed elements using the result type's Eq instance.

Duplicate transformed values are consolidated, so the resulting set may have fewer elements than s.

See also: hashset-filter, hashset-fold

hashset-filter

function ↑ Functions

(: hashset-filter (-> (-?-> %a bool) (HashSet %a) (HashSet %a)))
(hashset-filter keep? s)

Returns a new set containing only elements satisfying a predicate.

keep?
Predicate function returning #t to keep an element.
s
The source set.
returns
A new set of retained elements, using s's comparer.

See also: hashset-remove-all, hashset-find

hashset-fold

function ↑ Functions

(: hashset-fold (-> (-?-> %a %s %s) %s (HashSet %a) %s))
(hashset-fold f init s)

Folds over the elements of a set.

f
Accumulator function called as (f element acc), returning next acc.
init
Initial accumulator value.
s
The set to fold.
returns
The final accumulator value, or init if empty.
(hashset-fold + 0 (list->hashset (list 1 2 3)))   ; 6

Elements are visited in internal trie order.

See also: hashset-for-each, fold

hashset-for-each

function ↑ Functions

(: hashset-for-each (-> (-?-> %a void) (HashSet %a) void))
(hashset-for-each f s)

Applies a function to each element of a set.

f
Callback function invoked with each element.
s
The set to iterate over.

See also: hashset-iter, hashset-fold

hashset-iter

function ↑ Functions

(: hashset-iter (-> (-?-> %a bool) (HashSet %a) bool))
(hashset-iter f s)

Iterates over elements until a function returns #f.

f
Callback function returning #f to stop iteration.
s
The set to iterate over.
returns
#t if all elements were visited; #f if stopped early by f.

See also: hashset-for-each, hashset-any?, hashset-find

hashset-any?

function ↑ Functions

(: hashset-any? (-> (-> %a bool) (HashSet %a) bool))

Tests if any element satisfies a predicate.

pred
Predicate function.
s
The set to inspect.
returns
#t on the first element satisfying pred; #f if none match.

See also: hashset-find, hashset-iter

hashset-find

function ↑ Functions

(: hashset-find (-> (-> %a bool) (HashSet %a) (out %a) (Option %a)))

Returns the first element matching a predicate, or None.

pred
Predicate function.
s
The set to search.
returns
(Some element) for the first match, or None.

Finds the first match in internal trie traversal order. Because hash sets are unordered, matches are non-deterministic when multiple elements satisfy pred.

See also: hashset-any?, hashset-filter

list->hashset

function ↑ Functions

(: list->hashset (-> (List %a) (HashSet %a)))
(list->hashset xs)

Constructs a persistent hash set from a list.

xs
Source list. Duplicate elements are added once.
returns
A new persistent hash set.

See also: hashset->list, vec->hashset, seq->hashset, HashSetting

hashset->list

function ↑ Functions

(: hashset->list (-> (HashSet %a) (List %a)))
(hashset->list s)

Converts a set to a list in arbitrary order.

s
The source set.
returns
A list of elements in internal trie order.

See also: list->hashset, hashset->vec, hashset->seq

vec->hashset

function ↑ Functions

(: vec->hashset (-> (Vec %a) (HashSet %a)))
(vec->hashset v)

Constructs a persistent hash set from a vector.

v
Source vector. Duplicate elements are added once.
returns
A new persistent hash set.

See also: hashset->vec, list->hashset, seq->hashset

hashset->vec

function ↑ Functions

(: hashset->vec (-> (HashSet %a) (Vec %a)))
(hashset->vec s)

Converts a set to a vector in arbitrary order.

s
The source set.
returns
A vector of elements in internal trie order.

See also: vec->hashset, hashset->list, hashset->seq

seq->hashset

function ↑ Functions

(: seq->hashset (-> (Seq %a) (HashSet %a)))
(seq->hashset xs)

Constructs a persistent hash set from a sequence.

xs
Source sequence. Duplicate elements are added once.
returns
A new persistent hash set.

Constructed through a builder in a single pass.

See also: hashset->seq, list->hashset, vec->hashset

hashset->seq

function ↑ Functions

(: hashset->seq (-> (HashSet %a) (Seq %a)))

Views the elements of a set as a sequence.

s
The source set.
returns
A sequence of elements in internal trie order.

See also: seq->hashset, hashset->list

hashset->str

function ↑ Functions

(: hashset->str (-> (HashSet %a) string))
(hashset->str s)

Deprecated: use displayed. Formats a hash set as text in the form #{…}.

s
The set to format.
returns
String with elements formatted by displayed inside #{...}, separated by spaces.
(displayed (list->hashset (list 1)))   ; #{1}

The same text as displayed gives for a hash set. Elements appear in internal trie order. No reader macro reads this text back into a set.

See also: hashset->list

hashsetbuilder-empty

function ↑ Functions

(: hashsetbuilder-empty (-> (HashSetBuilder %a)))
(hashsetbuilder-empty)

Creates an empty hash set builder.

returns
A new builder using the element type's Eq instance.

See also: hashset->hashsetbuilder, hashsetbuilder-add!, HashSetBuilder

hashset->hashsetbuilder

function ↑ Functions

(: hashset->hashsetbuilder (-> (HashSet %a) (HashSetBuilder %a)))

Creates a hash set builder initialized with elements from a set.

s
The source set (unmodified).
returns
A new builder containing s's elements, using s's comparer.

Traverses the set to populate the buffer in O(n) time. To mutate an existing set in place, use hashset->transienthashset in O(1).

See also: hashsetbuilder-empty, hashset->transienthashset

hashsetbuilder-add!

function ↑ Functions

(: hashsetbuilder-add! (-> (HashSetBuilder %a) %a void))

Appends an element to a hash set builder buffer.

b
The builder.
x
The element to append.

See also: hashsetbuilder-add-all!, hashsetbuilder->hashset, add!

hashsetbuilder-add-all!

function ↑ Functions

(: hashsetbuilder-add-all! (-> (HashSetBuilder %a) (Seq %a) void))

Appends all elements of a sequence to a hash set builder buffer.

b
The builder.
xs
Sequence of elements to append.

See also: hashsetbuilder-add!

hashsetbuilder-length

function ↑ Functions

(: hashsetbuilder-length (-> (HashSetBuilder %a) int))

Returns the number of elements appended to the builder buffer.

b
The builder.
returns
The count of elements appended, including duplicates.

Duplicate entries are deduplicated when the set is constructed, so this value represents an upper bound on final set size.

See also: hashsetbuilder->hashset

hashsetbuilder->hashset

function ↑ Functions

(: hashsetbuilder->hashset (-> (HashSetBuilder %a) (HashSet %a)))

Constructs a persistent hash set from the builder buffer.

b
The builder.
returns
A new persistent hash set containing the appended elements.

See also: hashsetbuilder-empty, HashSetBuilder

transienthashset-empty

function ↑ Functions

(: transienthashset-empty (-> (TransientHashSet %a)))
(transienthashset-empty)

Creates an empty transient hash set.

returns
A new transient hash set using the element type's Eq instance.

See also: hashset->transienthashset, TransientHashSet

hashset->transienthashset

function ↑ Functions

(: hashset->transienthashset (-> (HashSet %a) (TransientHashSet %a)))

Creates a transient hash set from an existing persistent set.

s
The source set (unmodified).
returns
A mutable transient set that updates in place in O(1) time.

Shares nodes with s without copying. The transient performs copy-on-write on individual nodes as they are mutated.

See also: transienthashset->hashset, transienthashset-empty

transienthashset->hashset

function ↑ Functions

(: transienthashset->hashset (-> (TransientHashSet %a) (HashSet %a)))

Converts a transient hash set into a persistent set in O(1) time.

t
The transient hash set (remains usable).
returns
A new immutable persistent hash set.

Relinquishes ownership of current nodes to the persistent set. Subsequent writes to t perform copy-on-write without affecting the returned set.

See also: hashset->transienthashset

transienthashset-add!

function ↑ Functions

(: transienthashset-add! (-> (TransientHashSet %a) %a void))

Adds an element to a transient hash set in place.

t
The transient set to modify.
x
The element to add.

See also: transienthashset-add-all!, hashset-add, add!

transienthashset-add-all!

function ↑ Functions

(: transienthashset-add-all! (-> (TransientHashSet %a) (Seq %a) void))

Adds all elements of a sequence to a transient hash set in place.

t
The transient set to modify.
xs
Sequence of elements to add.

See also: transienthashset-add!, hashset-add-all

transienthashset-remove!

function ↑ Functions

(: transienthashset-remove! (-> (TransientHashSet %a) %a void))

Removes an element from a transient hash set in place.

t
The transient set to modify.
x
The element to remove.

See also: transienthashset-remove-all!, hashset-remove

transienthashset-remove-all!

function ↑ Functions

(: transienthashset-remove-all! (-> (TransientHashSet %a) (Seq %a) void))

Removes all elements of a sequence from a transient hash set in place.

t
The transient set to modify.
xs
Sequence of elements to remove.

See also: transienthashset-remove!, hashset-remove-all

transienthashset-contains?

function ↑ Functions

(: transienthashset-contains? (-> (TransientHashSet %a) %a bool))

Tests if an element is in the transient hash set.

t
The transient set.
x
The element to locate.
returns
#t if present, otherwise #f.

See also: hashset-contains?, ref

transienthashset-length

function ↑ Functions

(: transienthashset-length (-> (TransientHashSet %a) int))

Returns the number of elements in the transient hash set.

t
The transient set.
returns
Current count of elements.

See also: transienthashset-empty?, hashset-length

transienthashset-empty?

function ↑ Functions

(: transienthashset-empty? (-> (TransientHashSet %a) bool))

Tests if the transient hash set contains no elements.

t
The transient set.
returns
#t if empty, otherwise #f.

See also: transienthashset-length, hashset-empty?