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