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