Skip to main content

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​

empty :: Set(a).

singleton​

singleton :: a -> Set(a).

fromList​

fromList :: @{Comparable(a)}: [a] -> Set(a).

Inserts values from left to right and removes duplicates. This is O(n log n).

toList​

toList :: Set(a) -> [a].

Returns values in ascending order in O(n).

Querying​

size​

size :: Set(a) -> Int.

isEmpty​

isEmpty :: Set(a) -> Bool.

contains​

contains :: @{Comparable(a)}: Set(a) -> a -> Bool.

Updating and combining​

insert​

insert :: @{Comparable(a)}: Set(a) -> a -> Set(a).

Inserting a duplicate does not change the set.

remove​

remove :: @{Comparable(a)}: Set(a) -> a -> Set(a).

Removes a value when present. An absent value returns an equivalent set. This is O(log n).

union​

union :: @{Comparable(a)}: Set(a) -> Set(a) -> Set(a).

Returns every value present in either set. The implementation is O(m log(n + m)) for inputs of sizes n and m.

intersection​

intersection :: @{Comparable(a)}: Set(a) -> Set(a) -> Set(a).

Returns values present in both sets. This is O(n × (log n + log m)) worst case.

difference​

difference :: @{Comparable(a)}: Set(a) -> Set(a) -> Set(a).

Returns values from the first set that are absent from the second. This is O(n × (log n + log m)) worst case.

isSubset​

isSubset :: @{Comparable(a)}: Set(a) -> Set(a) -> Bool.

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​

filter :: @{Comparable(a)}: Set(a) -> (a -> Bool) -> Set(a).

Keeps values whose predicate returns True. Callbacks run in ascending order; rebuilding the result is O(n log n) worst case.

map​

map :: @{Comparable(b)}: Set(a) -> (a -> b) -> Set(b).

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​

foldLeft :: Set(a) -> b -> (b -> a -> b) -> b.

Folds values from least to greatest in O(n) plus callback work.

foldRight​

foldRight :: Set(a) -> b -> (a -> b -> b) -> b.

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.