3.8 sets

contents ← prev up next →

3.8 sets🔗

Usage:

include sets

import sets as ...

3.8.1 The Set Type🔗

Set<a>

There are two underlying representations that sets may have:

List-based sets work on all values that can be compared with the equal-always built-in function (this means that, for example, a set of functions won’t work). List-based sets perform up to n comparisons on addition, removal, and membership testing, where n is the number of elements in the set. (In order to give this guarantee, list-based sets don’t store duplicates; they avoid this by scanning the whole list on addition.)
Tree-based sets require that all elements implement the _lessthan method in order to perform comparisons, and guarantee that only up to log(n) less-than comparisons will be performed for a set with n elements on addition, removal, and membership testing.

There are no variants for Sets, and programs cannot use cases statements with Sets. Instead, they can be created with the constructors below, and manipulated with the methods and functions below.

Some methods, like .union, combine multiple sets. The set on the left-hand side is the representation of the result. For example, in

[list-set: 1, 2].union([tree-set: 3, 4])

the result will be a list-set.

3.8.2 Using Sets in Programs🔗

Some of the names provided for sets tend to overlap with those provided for lists. The latter are built-in. Therefore, using the include form is likely to cause name-clashes. It is wiser to import sets using a prefix name and use the names below through that prefix.

Examples:

import sets as S

check:
  S.list-to-list-set([list: 1, 2, 1, 2]) is [S.list-set: 2, 1]
end

3.8.3 Set Constructors🔗

[list-set: elt :: a, ...] -> Set<a>

Constructs a set out of the elts, representing them as a list. Raises an exception if the elements don’t support equality.

Examples:

import sets as S

check:
  [S.list-set: 1, 2, 3] is [S.list-set: 1, 2, 3]
  [S.list-set: 1, 2, 2] is [S.list-set: 1, 2]
  [S.list-set: [list: 1], [list: 1], [list: 2]] is
    [S.list-set: [list: 2], [list: 1]]
end

empty-list-set :: Set<a>

An empty set, represented as a list.

[tree-set: elt :: a, ...] -> Set<a>

Constructs a set out of the elts, representing them as a tree. Raises an exception if the elements don’t support the < operator via _lessthan.

Examples:

import sets as S

check:
  [S.tree-set: 1, 2, 3] is [S.tree-set: 1, 2, 3]
  [S.tree-set: 1, 2, 2] is [S.tree-set: 1, 2]
  [S.tree-set: [list: 1], [list: 1], [list: 2]] raises "binop-error"
end

empty-tree-set :: Set<a>

An empty set, represented as a tree.

[set: elt :: a, ...] -> Set<a>

Another name for list-set.

list-to-list-set :: (lst :: List<a>) -> Set<a>

Constructs a list-set out of the elements in the list.

Examples:

import sets as S

check:
  s1 = S.list-to-list-set([list: 1, 2, 3, 3, 3])
  s1 is [S.list-set: 1, 2, 3]
end

list-to-tree-set :: (lst :: List<a>) -> Set<a>

Constructs a tree-set out of the elements in the list.

Examples:

import sets as S

check:
  s1 = S.list-to-tree-set([list: 1, 2, 3, 3, 3])
  s1 is [S.tree-set: 1, 2, 3]
end

list-to-set :: (lst :: List<a>) -> Set<a>

Another name for list-to-list-set.

3.8.4 Set Methods🔗

.add :: (elt :: a) -> Set<a>

Constructs a new set containing the added element if it was not already present.

Examples:

import sets as S

check:
  s1 = [S.set: 1, 2, 3]
  s2 = s1.add(4)
  s3 = s1.add(1)
  s2 is-not s1
  s3 is s1
  s1.size() is 3
  s2.size() is 4
  s3.size() is 3
end

.remove :: (elt :: a) -> Set<a>

Constructs a new set removing the element if it was present. It is not an error to remove an element that is not in the set; it simply leaves the set unchanged.

Examples:

import sets as S

check:
  s1 = [S.set: 1, 2, 3]
  s2 = s1.remove(3)
  s3 = s1.remove(4)
  s2 is-not s1
  s3 is s1
  s1.size() is 3
  s2.size() is 2
  s3.size() is 3
end

.size :: () -> Number

Computes the number of elements in the set.

Examples:

import sets as S

check:
  [S.set: 1, 2, 3].size() is 3
  [tree-set: 1, 2, 3].size() is 3
  [list-set: 1, 2, 3].size() is 3
end

.member :: (elt :: a) -> Boolean

Checks if elt is contained within this set (checking membership with equal-always).

Examples:

import sets as S

check:
  s1 = [S.set: 1, 2, 3]
  s1.member(1) is true
  s1.member(4) is false
end

.pick :: () -> Pick<a, Set<a>>

Picks an arbitrary element out of the set, and returns a Pick data structure. If the set is empty, then .pick returns a pick-none. Otherwise it returns a pick-some, whose elt field stores the picked value and whose rest field stores the rest of the set.

Examples:

import sets as S
import pick as P

check:
  fun sum-of-set(s :: S.Set):
    cases(P.Pick) s.pick():
      | pick-none => 0
      | pick-some(elt, rest) => elt + sum-of-set(rest)
    end
  end

  sum-of-set([S.set: 1, 2, 3, 4]) is 10
  sum-of-set([S.tree-set: 1, 2, 3, 4]) is 10

  [S.set:].pick() is P.pick-none
  [S.set: 1].pick() is P.pick-some(1, S.empty-list-set)
end

It is very important to note that the order of elements returned from .pick is non-deterministic, so multiple calls to .pick may not produce the same result for the same set! Thus, in the following program:

Examples:

import sets as S
import pick as P

check:
  [S.set: 1, 2].pick() is P.pick-some(1, [S.set: 2])
  [S.set: 1, 2].pick() is P.pick-some(2, [S.set: 1])
end

Sometimes both tests will pass, sometimes one will pass and the other fail, and sometimes both tests will fail! We can, however, write the following tests that will always pass:

Examples:

import sets as S
import pick as P

check:
  fun one-of(e, l): l.member(e) end

  [S.set: 1, 2].pick().elt is%(one-of) [list: 1, 2]
  [S.set: 1, 2].pick().rest is%(one-of)
  [list: [S.set: 1], [S.set: 2]]
end

.union :: (other :: Set<a>) -> Set<a>

Computes the union of two sets.

Examples:

import sets as S

check:
  [S.list-set: 1, 2, 3].union([S.tree-set: 2, 3, 4])
    is [S.list-set: 1, 2, 3, 4]

  S.empty-tree-set.union([S.list-set: 3, 4, 4])
    is [S.tree-set: 3, 4]
end

.intersect :: (other :: Set<a>) -> Set<a>

Computes the intersection of two sets.

Examples:

import sets as S

check:
  [S.list-set: 1, 2, 3].intersect([S.tree-set: 2, 3, 4])
    is [S.list-set: 2, 3]

  S.empty-tree-set.intersect([S.list-set: 3, 4, 4])
    is [S.tree-set: ]
end

.difference :: (other :: Set<a>) -> Set<a>

Computes the difference of two sets.

Examples:

import sets as S

check:
  [S.list-set: 1, 2, 3].difference([S.tree-set: 2, 3, 4])
    is [S.list-set: 1]

  S.empty-tree-set.difference([S.list-set: 3, 4, 4])
    is [S.tree-set: ]
end

.symmetric-difference :: (other :: Set<a>) -> Set<a>

Computes the symmetric difference of two sets.

Examples:

import sets as S

check:
  [S.list-set: 1, 2, 3].symmetric-difference([S.tree-set: 2, 3, 4])
    is [S.list-set: 1, 4]

  S.empty-tree-set.symmetric-difference([S.list-set: 3, 4, 4])
    is [S.tree-set: 3, 4]
end

.to-list :: () -> List<a>

Converts the set into a list. There is no guarantee about the order of elements in the list.

Examples:

import sets as S

check:
  [S.list-set: 3, 1, 4, 1, 5, 9, 2].to-list().length() is 6
  [S.tree-set: 8, 6, 7, 5, 3, 0, 9].to-list().length() is 7
end

.fold :: (f :: (b, a -> b), base :: b) -> b

Applies f to each element of the set along with the accumulator (starting with base) to produce a new value. Traverses elements in an unspecified order.

Examples:

import sets as S

check:
  fun one-of(e, l): l.member(e) end

  s = [S.tree-set: "1", "2", "3"]
  result = s.fold(string-append, "")

  result is%(one-of) [list: "123", "132", "213", "231", "312", "321"]
end

contents ← prev up next →

1	Getting Started
2	Language Concepts
3	Builtins and Libraries
4	Pyret Style Guide
5	Internals
6	Glossary

3.1	Global Utilities
3.2	Numbers
3.3	Strings
3.4	Booleans
3.5	Raw Array
3.6	Tables
3.7	lists
3.8	sets
3.9	arrays
3.10	string-dict
3.11	option
3.12	pick
3.13	either
3.14	srcloc
3.15	pprint
3.16	s-exp
3.17	s-exp-structs
3.18	color
3.19	image-structs
3.20	The image libraries
3.21	world
3.22	gdrive-sheets
3.23	data-source
3.24	reactors
3.25	chart
3.26	plot
3.27	statistics
3.28	math
3.29	matrices

3.8.1	The Set Type
3.8.2	Using Sets in Programs
3.8.3	Set Constructors
3.8.4	Set Methods