Sets

A set contains elements of the same type, without duplicates. Sets are constructed via the set constructor function, e.g., set[1, 2, 2, 3] creates a set of three integers 1, 2, 3. The expression set[] produces the empty set.

To add an element to a set, use the function insertElement, to remove an element, use remove. To test for set membership, use the function contains.

The takeMaybe function can be used to iterate through a set as follows:

def Unit printAll<A>(Set<A> set) =
  case takeMaybe(set) {
    Nothing => println("Finished")
    | Just(e) => let (Unit dummy) = println("Element " + toString(e)) in printAll(remove(set, e))
  };

Alternatively, map and other functions that operate on lists, as well as the foreach statement, can be used on sets by obtaining a list of the set’s elements via the elements function.

Datatypes and constructors

The datatype for sets with elements of type A is Set<A>. The set constructor function is used to construct sets:

set[1, 2, 3, 3, 3]
// => set[1, 2, 3]

Functions

contains

Returns True if set ss contains element e, False otherwise.

contains(set[1, 2, 3], 2)
// => True

emptySet

Returns True if set xs is empty, False otherwise.

emptySet(set[])
// => True

size

Returns the number of elements in set xs.

size(set[1, 2, 3])
// => 3

elements

Returns a list with all elements in set xs.

elements(set[1, 2, 3])
// => list[1, 2, 3]

union

Returns a set containing all elements of sets set1 and set2.

union(set[1, 2, 3], set[4, 3, 5])
// => set[1, 2, 3, 4, 5]

intersection

Returns a set containing all elements that are present in both sets set1 and set2.

intersection(set[1, 2, 3], set[4, 3, 5])
// => set[3]

difference

Returns a set containing all elements of set set1 not present in set set2.

difference(set[1, 2, 3], set[4, 3, 5])
// => set[1, 2]

isSubset

Returns True if set contains all elements of maybe_subset, False otherwise.

isSubset(set[1], set[1, 2, 3])
// => True

insertElement

Returns a set with all elements of set xs plus element e. Returns a set with the same elements as xs if xs already contains e.

insertElement(set[2, 3], 1)
// => set[1, 2, 3]

remove

Returns a set with all elements of set xs except element e. Returns a set with the same elements as xs if xs did not contain e.

remove(set[1, 2, 3], 1)
// => set[2, 3]

take

Returns one element from a non-empty set. It is an error to call take on an empty set; consider using takeMaybe in that case.

take(set[1, 2, 3])
// => 1 // or 2 or 3

takeMaybe

Returns Just wrapping one element from a set, or Nothing for an empty set.

takeMaybe(set[1, 2, 3])
// => Just(1) // or Just(2) or Just(3)
takeMaybe(set[])
// => Nothing