►Pyret
▼3 Builtins and Libraries
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 image-structs
3.19 image
3.20 world
3.21 gdrive-sheets
3.22 data-source
3.23 reactors
3.24 chart
3.25 plot
3.26 statistics
3.27 math
►3.8 sets
On this page:
3.8.1 The Set Type
Set
3.8.2 Set Constructors
list-set
empty-list-set
tree-set
empty-tree-set
set
list-to-list-set
list-to-tree-set
list-to-set
3.8.3 Set Methods
.add
.remove
.size
.member
.pick
.union
.intersect
.difference
.symmetric-difference
.to-list
.fold
    ← prev  up  next → 

3.8 sets

Usage:
include sets
import sets as ...
The interface to sets is in flux, and its design may change significantly in the future.

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 removal, addition, 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 duplicate elements by scanning the whole list on insertion). 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 removal, addition, 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 Set Constructors
[list-set: elt :: a, ...] -> Set<a>

Constructs a set out of the elts.

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

empty-list-set :: Set<a>

An empty set.

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

Constructs a set out of the elts backed by a tree. Raises an exception if the elements don’t support the < operator via _lessthan.

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

empty-tree-set :: Set<a>

An empty set backed by a tree.

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

Another name for list-set.

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

Turn a list into a list-set.

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

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

Turn a list into a tree-set.

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

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

Another name for list-to-list-set.

3.8.3 Set Methods

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

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

.size :: () -> Number

Get the number of elements in the set.

Examples:
check:
  [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).

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

Picks an arbitrary element out of the set, and returns a Pick data structure. If the set is empty, a pick-none is returned, otherwise a pick-some is returned, and the rest of the set (without the picked value) is stored in the rest field of the pick-some.

Examples:
import pick as P
check:
  fun pick-sum(s):
    cases(P.Pick) s.pick():
      | pick-none => 0
      | pick-some(elt, rest) => elt + pick-sum(rest)
    end
  end

  pick-sum([set: 1, 2, 3, 4]) is 10

  [set:].pick() is P.pick-none
end

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.

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

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

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

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

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

.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:
check:
  fun one-of(ans, elts):
    lists.member(elts, ans)
  end
  t1 = [tree-set: "1", "2", "3"]
  result = t1.fold(string-append, "")

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

    ← prev  up  next →