std::sets
Import with import std::sets.
Exports
Section titled “Exports”Types
struct Set
Section titled “struct Set”struct Set<T>
opaque — construction surface is private to its defining module
A collection of values with no duplicates. Write one as Set[1, 2, 3],
or as a list literal where a Set is expected. A set is immutable:
Set.insert and Set.remove return a new set. It keeps its elements in
the order they were first added, and two sets with the same elements are
equal whatever their order.
Set.contains tests membership. a + b is the union of two sets
(Set.union) and a - b their difference (Set.difference).
Iter.to_set collects any sequence into a set, dropping repeats.
fruits = Set["apple", "pear"]
assert Set.contains(fruits, "pear")
refute Set.contains(fruits, "plum")
assert Set.insert(fruits, "apple") == fruits
assert Set["a", "b"] == Set["b", "a"]
assert [1, 2, 2, 3] |> Iter.to_set() == Set[1, 2, 3]
Set.insert
Section titled “Set.insert”fn insert<T>(s: Set<T>, elem: T) -> Set<T>
type function on Set
s with elem added. A set that already holds elem comes back
unchanged.
assert Set.insert([1, 2], 3) == [1, 2, 3]
assert Set.insert([1, 2], 2) == [1, 2]
Set.remove
Section titled “Set.remove”fn remove<T>(s: Set<T>, elem: T) -> Set<T>
type function on Set
s without elem. A set that does not hold elem comes back
unchanged.
assert Set.remove([1, 2, 3], 2) == [1, 3]
assert Set.remove([1, 2], 9) == [1, 2]
Set.size
Section titled “Set.size”fn size<T>(s: Set<T>) -> NonNegativeInt
type function on Set
The number of elements. The set stores its count, so this does not walk the elements.
assert Set.size([1, 2, 3]) == 3
empty: Set<Int> = []
assert Set.size(empty) == 0
Set.union
Section titled “Set.union”fn union<T>(a: Set<T>, b: Set<T>) -> Set<T>
type function on Set
The elements that are in a, in b or in both. a + b is the same
call.
assert Set.union([1, 2], [2, 3]) == [1, 2, 3]
Set.intersection
Section titled “Set.intersection”fn intersection<T>(a: Set<T>, b: Set<T>) -> Set<T>
type function on Set
The elements that are in both a and b.
assert Set.intersection([1, 2], [2, 3]) == [2]
assert Set.intersection([1, 2], [3]) == []
Set.difference
Section titled “Set.difference”fn difference<T>(a: Set<T>, b: Set<T>) -> Set<T>
type function on Set
The elements of a that are not in b. a - b is the same call.
assert Set.difference([1, 2, 3], [2]) == [1, 3]
Set.is_subset_of
Section titled “Set.is_subset_of”fn is_subset_of<T>(a: Set<T>, b: Set<T>) -> Bool
type function on Set
True if every element of a is also in b. The empty set is a subset
of every set, and a set is a subset of itself.
assert Set.is_subset_of([1, 2], [1, 2, 3])
refute Set.is_subset_of([1, 4], [1, 2, 3])
assert Set.is_subset_of([], [1])
Set.contains
Section titled “Set.contains”impl Contains for Set<T>
fn contains(c: Set<T>, x: T) -> Bool
impl Contains.contains
True if x is a member of the set: a hash lookup.
assert Set.contains(Set[1, 2], 1)
refute Set.contains(Set[1, 2], 9)
empty: Set<Int> = []
refute Set.contains(empty, 1)
Set.each_while
Section titled “Set.each_while”impl Iter for Set<T>
fn each_while(s: Set<T>, yield: (T) -> Bool) -> Bool
impl Iter.each_while
A Set iterates its elements in the order they were first added:
Iter.to_list(Set[3, 1, 2]) is [3, 1, 2]. Pushes each element to
yield, stopping when it returns False.
Set.known_count
Section titled “Set.known_count”impl Iter for Set<T>
fn known_count(s: Set<T>) -> Maybe<Int>
impl Iter.known_count
Set.to_string
Section titled “Set.to_string”impl Display for Set<T>
fn to_string(s: Set<T>) -> String
impl Display.to_string
Set.inspect
Section titled “Set.inspect”impl Debug for Set<T>
fn inspect(s: Set<T>) -> String
impl Debug.inspect
Set.equal
Section titled “Set.equal”impl Equatable for Set<T>
fn equal(a: Set<T>, b: Set<T>) -> Bool
impl Equatable.equal
Set.hash
Section titled “Set.hash”impl Hashable for Set<T>
fn hash(s: Set<T>) -> Int
impl Hashable.hash
Set.add
Section titled “Set.add”impl Add<Set<T>, Set<T>> for Set<T>
fn add(a: Set<T>, rhs: Set<T>) -> Set<T>
impl Add.add
a + b is Set.union(a, b).
assert Set[1, 2] + Set[2, 3] == [1, 2, 3]
assert Set[1] + Set[2] == [1, 2]
Set.empty_sum
Section titled “Set.empty_sum”impl Summable for Set<T>
fn empty_sum() -> Set<T>
impl Summable.empty_sum
The sum of no Sets: the empty Set. Summing Sets is their union.
empty: Set<Int> = Set.empty_sum()
assert Set.size(empty) == 0
assert Set[1, 2] + Set.empty_sum() == [1, 2]
assert Iter.sum([Set[1, 2], Set[2, 3]]) == [1, 2, 3]
Set.subtract
Section titled “Set.subtract”impl Subtract<Set<T>, Set<T>> for Set<T>
fn subtract(a: Set<T>, rhs: Set<T>) -> Set<T>
impl Subtract.subtract
a - b is Set.difference(a, b).
assert Set[1, 2, 3] - Set[2] == [1, 3]
assert Set[1, 2] - Set[9] == [1, 2]
type NonEmptySet
Section titled “type NonEmptySet”subtype NonEmptySet<T> Set<T> when fn s -> Set.size(s) > 0
A Set with at least one element. A literal is checked when the program
is compiled; NonEmptySet.try_from(s) checks a Set computed at run
time, and NonEmptySet.insert(s, item) builds one from any Set. Its
smallest and largest elements are values rather than Maybes. A
NonEmptySet is a Set and passes wherever one is expected. It is in the
prelude.
subtype: NonEmptySet is a subtype of Set<T>. A literal where a NonEmptySet is expected is checked when the program is compiled; NonEmptySet.try_from(...) checks a value when it runs.
tags: NonEmptySet<String> = ["b", "a"]
assert NonEmptySet.min(tags) == "a"
assert Set.size(tags) == 2
none: Set<String> = []
assert NonEmptySet.try_from(none) == None
NonEmptySet.of
Section titled “NonEmptySet.of”fn of<T>(first: T, rest: Set<T>) -> NonEmptySet<T>
type function on NonEmptySet
A NonEmptySet of first and the elements of rest, which may be
empty.
assert NonEmptySet.of(1, Set[2, 1]) == Set[1, 2]
NonEmptySet.size
Section titled “NonEmptySet.size”fn size<T>(s: NonEmptySet<T>) -> PositiveInt
type function on NonEmptySet
The number of elements, at least one.
assert NonEmptySet.size(["a", "b"]) == 2
NonEmptySet.max
Section titled “NonEmptySet.max”fn max<T>(s: NonEmptySet<T>) -> T where T: Comparable
type function on NonEmptySet
The largest element.
assert NonEmptySet.max([3, 9, 4]) == 9
NonEmptySet.min
Section titled “NonEmptySet.min”fn min<T>(s: NonEmptySet<T>) -> T where T: Comparable
type function on NonEmptySet
The smallest element.
assert NonEmptySet.min([3, 9, 4]) == 3
NonEmptySet.map
Section titled “NonEmptySet.map”fn map<T, U>(s: NonEmptySet<T>, f: (T) -> U) -> NonEmptySet<U>
type function on NonEmptySet
Applies f to each element; equal results collapse to one.
assert NonEmptySet.map([1, 2, 3], fn n -> n % 2) == Set[1, 0]
NonEmptySet.to_list
Section titled “NonEmptySet.to_list”fn to_list<T>(s: NonEmptySet<T>) -> NonEmptyList<T>
type function on NonEmptySet
The elements as a NonEmptyList, in the set’s order.
assert NonEmptySet.to_list(["a", "b"]) == ["a", "b"]
NonEmptySet.insert
Section titled “NonEmptySet.insert”fn insert<T>(s: Set<T>, item: T) -> NonEmptySet<T>
type function on NonEmptySet
s, which may be empty, with item added.
assert NonEmptySet.insert(Set[1], 2) == Set[1, 2]
empty: Set<Int> = []
assert NonEmptySet.insert(empty, 2) == Set[2]
NonEmptySet.union
Section titled “NonEmptySet.union”fn union<T>(a: NonEmptySet<T>, b: Set<T>) -> NonEmptySet<T>
type function on NonEmptySet
The elements of a and of b, which may be empty.
assert NonEmptySet.union([1], Set[2]) == Set[1, 2]
NonEmptySet.try_from
Section titled “NonEmptySet.try_from”fn try_from<T>(value: Set<T>) -> Maybe<NonEmptySet<T>>
type function on NonEmptySet
Some of the value when it satisfies NonEmptySet’s rules, None when it does not.