Set
Import Set for unique, ordered values. Values require Comparable(a), and views
traverse them in ascending order. The representation and constructor are
private. Membership and single-value updates are O(log n); ordered traversal
is O(n).
Type
Set
Set(a) stores at most one occurrence of each value of type a.
Construction
empty
singleton
fromList
Inserts values from left to right and removes duplicates. This is
O(n log n).
toList
Returns values in ascending order in O(n).
Querying
size
isEmpty
contains
Updating and combining
insert
Inserting a duplicate does not change the set.
remove
Removes a value when present. An absent value returns an equivalent set. This
is O(log n).
union
Returns every value present in either set. The implementation is
O(m log(n + m)) for inputs of sizes n and m.
intersection
Returns values present in both sets. This is O(n × (log n + log m)) worst
case.
difference
Returns values from the first set that are absent from the second. This is
O(n × (log n + log m)) worst case.
isSubset
Returns whether every value in the first set occurs in the second. After a
missing value is found, later membership lookups are skipped, but traversal of
the first set continues. This is O(n log m) worst case.
Transforming and traversal
filter
Keeps values whose predicate returns True. Callbacks run in ascending order;
rebuilding the result is O(n log n) worst case.
map
Transforms values in ascending input order and rebuilds ordering for b.
Duplicate outputs collapse to one value. This is O(n log n) plus callback
work.
foldLeft
Folds values from least to greatest in O(n) plus callback work.
foldRight
Folds values from greatest to least in O(n) plus callback work.
Generic methods
Importing Set supplies Reducible without an element ordering constraint and Combinable when elements are Comparable. Set has no Mappable instance. Use its collection-first map for ordered, deduplicated output, or convert with Set::toList before generic mapping.