Set

From the SETL Wiki

Introduction

The set type is probably the most important built-in type in SETL, and the type after which the language is named. A set represents a finite set of arbitrary values. Any value can be an element of a set, and sets can contain elements of mixed types (unless a repr declaration prohibits it.)

Sets are unordered, i.e. the order in which elements were inserted cannot be determined from the set alone.

Sets are idempotent, i.e. inserting an element two or more times is equivalent to inserting it once. Similarly removing an element two or more times is equivalent to removing it once. Also it is not possible to detect just by examining the set that an element has been added and subsequently removed.

Operations on sets

The empty set

The simplest set is of course the empty set, denoted by {}.

Creating new sets

Sets can be created by enumerating the elements (or expressions that evaluate to elements) e.g. {2, 3+1, 4, 5+1} or equivalently {2, 4, 6}.

Inserting and removing elements

The with operator adds the value on its left to the set on its right, e.g.

• {1, 2} with 3 = {1, 2, 3}
• {1, 2} with 2 = {1, 2}

Deriving new sets from existing sets

New sets can be derived by

• Comprehension, i.e. evaluating an expression, substituting each element of an existing set in turn, and inserting each result into the new set, e.g. {x * x: x in {1, 2, 3}} yields {1, 4, 9}.
• If the existing set is a map, the domain and range operators return new sets containing the map's keys and values respectively.
• The pow operator computes the powerset of a set, e.g. pow {1, 2} = {{}, {1}, {2}, {1, 2}}. See also npow.

Set arithmetic

• Set union is denoted in SETL by the + operator, e.g. {1, 2} + {2, 3} = {1, 2, 3}
• Set intersection is denoted by the * operator, e.g. {1, 2} * {2, 3} = {2}
• Asymmetric set difference is denoted by the - operator, e.g. {1, 2} - {2, 3} = {1}
• Symmetric set difference is denoted by the mod operator, e.g. {1, 2} mod {2, 3} = {1, 3}

Other operations using sets

The # operator returns the cardinality of a set.

The arb operator selects an arbitrary element from a non-empty set. Exactly which element is selected is unpredictable.

As well as being used in comprehensions (see above) iterators can be used to loop over the elements of the set in an undefined order, e.g.

(for x in {1, 2, 3})
  print(x);
end;

for x in {1, 2, 3} loop
  print(x);
end;

Will print 1, 2 and 3 on separate lines, in an unpredictable order.

Set predicates

• The in and notin operators test whether or not a value is a member of a set.
• The subset and incs operators test whether one set is a subset of another.
• The is_set predicate returns true for all sets and false for all non-set values.

Notes

• om cannot normally be a member of a set, though there is a way to construct a set containing om in SETL2.