Skip to content

std::sets

Import with import std::sets.

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]
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]
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]
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
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]
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]) == []
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]
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])

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)

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.

impl Iter for Set<T>

fn known_count(s: Set<T>) -> Maybe<Int>

impl Iter.known_count

impl Display for Set<T>

fn to_string(s: Set<T>) -> String

impl Display.to_string

impl Debug for Set<T>

fn inspect(s: Set<T>) -> String

impl Debug.inspect

impl Equatable for Set<T>

fn equal(a: Set<T>, b: Set<T>) -> Bool

impl Equatable.equal

impl Hashable for Set<T>

fn hash(s: Set<T>) -> Int

impl Hashable.hash

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]

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]

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]
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
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]
fn size<T>(s: NonEmptySet<T>) -> PositiveInt

type function on NonEmptySet

The number of elements, at least one.

assert NonEmptySet.size(["a", "b"]) == 2
fn max<T>(s: NonEmptySet<T>) -> T where T: Comparable

type function on NonEmptySet

The largest element.

assert NonEmptySet.max([3, 9, 4]) == 9
fn min<T>(s: NonEmptySet<T>) -> T where T: Comparable

type function on NonEmptySet

The smallest element.

assert NonEmptySet.min([3, 9, 4]) == 3
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]
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"]
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]
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]
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.