▼ 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.1 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.2 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.8 sets

#### 3.8sets

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

##### 3.8.1The 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.2Set 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```

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```

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.3Set 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```