3.8 sets
3.8.1 The Set Type
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
Constructs a set out of the elts.
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.
Constructs a set out of the elts backed by a tree. Raises an exception if the elements don’t support the < operator via _lessthan.
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.
Another name for list-set.
Turn a list into a list-set.
check: s1 = sets.list-to-list-set([list: 1, 2, 3, 3, 3]) s1 is [list-set: 1, 2, 3] end
Turn a list into a tree-set.
check: s1 = sets.list-to-tree-set([list: 1, 2, 3, 3, 3]) s1 is [tree-set: 1, 2, 3] end
Another name for list-to-list-set.
3.8.3 Set Methods
Get the number of elements in the set.
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
Checks if elt is contained within this set (checking membership with equal-always).
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.
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.
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.
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