std/set
Sets: collections of values with no two the same, which may not be changed.
A Set(A) is a Dict(A, Nil) (see std/dict): members are compared
with == and found by their core.hash, so any value may be a member.
insert, delete, and contains take O(log n) steps. Two sets with the
same members are ==. The order of to_list and fold is not fixed.
Set
A set of values of type a.
Set(A) = (Dict(A, Nil)) new
A set with no members.
new = <A>() -> Set(A) { Set(dict.new()) } size
The number of members. This takes one step.
size = <A>(set : Set(A)) -> Int { is_empty
True when the set has no members.
is_empty = <A>(set : Set(A)) -> Bool { size(set) == 0 } insert
The set with a new member. If it is already there, the set is the same.
insert = <A>(into : Set(A), this : A) -> Set(A) { delete
The set without a member.
delete = <A>(from : Set(A), this : A) -> Set(A) { contains
True when this is a member.
contains = <A>(in : Set(A), this : A) -> Bool { to_list
The members, in the order of fold.
to_list = <A>(set : Set(A)) -> List(A) { from_list
A set of the elements of a list.
set.from_list([1, 2, 1]) |> set.size // 2 from_list = <A>(members : List(A)) -> Set(A) { fold
Combines every member with an accumulator. The order is not fixed.
fold = <A, Acc, N>( each
Calls a function with every member.
each = <A, B, N>(set : Set(A), with : (A) <- N -> B) -> Nil { map
The set of the values of a function on every member.
map = <A, B, N>(set : Set(A), with : (A) <- N -> B) -> Set(B) { filter
Keeps the members for which the function gives True.
filter = <A, N>(in : Set(A), keeping : (A) <- N -> Bool) -> Set(A) { take
Keeps only the members that are in the list.
take = <A>(from : Set(A), keeping : List(A)) -> Set(A) { drop
Takes out the members that are in the list.
drop = <A>(from : Set(A), drop : List(A)) -> Set(A) { union
The members of one or both sets.
union = <A>(of : Set(A), and : Set(A)) -> Set(A) { intersection
The members of both sets.
intersection = <A>(of : Set(A), and : Set(A)) -> Set(A) { difference
The members of from that are not in minus.
difference = <A>(from : Set(A), minus : Set(A)) -> Set(A) { symmetric_difference
The members of exactly one of the sets.
symmetric_difference = <A>(of : Set(A), and : Set(A)) -> Set(A) { is_subset
True when every member of first is in of.
is_subset = <A>(first : Set(A), of : Set(A)) -> Bool { is_disjoint
True when no member is in both sets.
is_disjoint = <A>(first : Set(A), from : Set(A)) -> Bool {