Set

A value of CSL’s built-in type Set a is a data structure that satisfy the conditions of sets, i.e., elements cannot occur more than once.

Like all other data in CSL, sets are immutable: inserting elements into or removing elements from sets does not alter the original sets themselves. To create a new set one must combine existing sets with one another or with new elements using the operations

  • element insertion Set::insert,
  • element removal Set::remove,
  • union \(A\cup{}B\) Set::union,
  • intersection \(A\cap{}B\) Set::intersection,
  • set difference \(A\setminus{}B\) Set::difference.

The empty set \(\emptyset\) is constructed with the funcition Set::empty. It is used as the basis for forming new sets – to obtain a set with a single element one adds an element to the empty set:

val mySet = Set::insert 1 Set::empty

The set mySet above is equivalent to the set \(\lbrace1\rbrace\).

Like CSL maps, sets are unordered.

Set::empty : Set v

Returns the empty set.

Set::insert : v -> Set v -> Set v

Returns a new set that contains, in addition to the elements already present in the argument set, the given element.

Examples

val emptySet = Set::empty
val oneElm = Set::insert 1 emptySet
val twoElms = Set::insert 2 oneElm

Set::remove : v -> Set v -> Set v

Returns a new set with the given element removed.

Examples

val mySet = Set::insert 1 Set::empty
val myEmptySet = Set::remove 1 mySet
//             = Set::empty
val mySet2 = Set::remove 2 mySet
//         = mySet

Set::fold : (v -> a -> a) -> a -> Set v -> a

Fold over the elements in a set.

Examples

val sumElems = Set::fold (\x -> \sum -> x + sum) 0
val s = sumElems (Set::fromList [1, 2, 3])
//    = 6

Set::contains : v -> Set v -> Bool

Returns True if the set contains the given value. Otherwise it returns False.

Examples

val mySet = Set::insert 1 Set::empty
val oneVal = Set::contains 1 mySet
//         = True
val twoVal = Set::contains 2 mySet
//         = False

Set::union : Set v -> Set v -> Set v

Take the union of two sets.

Examples

val setA = Set::fromList [1, 2]
val setB = Set::fromList [2, 3]
val setC = Set::union setA setB
//       = Set::fromList [1, 2, 3]

Set::intersection : Set v -> Set v -> Set v

Take the intersection of two sets.

Examples

val setA = Set::fromList [1, 2]
val setB = Set::fromList [2, 3]
val setC = Set::intersection setA setB
//       = Set::singleton 2

Set::difference : Set v -> Set v -> Set v

Take the difference between two sets.

Examples

val setA = Set::fromList [1, 2]
val setB = Set::fromList [2, 3]
val setC = Set::difference setA setB
//       = Set::fromList [1]

Set::singleton : v -> Set v

Constructs a singleton set with just one element.

Examples

val s = Set::singleton 1
//    = Set::fromList [1]

Set::fromList : List v -> Set v

Constructs a set with the elements in the given list.

Examples

val prices = Set::fromList [10, 12, 15]

Set::toList : Set v -> List v

Converts a set to a list. The ordering is unspecified and may change.

Examples

val l = [1, 2, 3, 1, 2]
val l2 = Set::toList (Set::fromList l)
//     = [1, 2, 3]

Set::size : Set v -> Int

Returns the size of a set.

Examples

val a = Set::size Set::empty
//    = 0
val b = Set::size (Set::fromList [1, 1, 2])
//    = 2