#set

An immutable set of distinct elements, ordered by Ord.

Set a is a balanced binary search tree. Membership, insertion, and deletion cost O(log n), and size is O(1). Every operation returns a new set and leaves the original unchanged; the two share whatever structure they have in common.

toList and the Foldable methods visit elements in ascending order. The Set { x, ... } literal builds a set; the empty set is empty. For elements that are Hashable but not Ord, or when order does not matter, see hash_set.

#Set

data Set a
  = Tip
  | Bin Int a (Set a) (Set a)

The set type.

Tip is the empty tree and Bin is an interior node holding its subtree's size, an element, and the left and right subtrees. The constructors are visible for pattern matching, but build sets with the functions in this module, which keep the tree balanced.

Instances: Foldable, Eq, Ord, Debug, Display, Semigroup, FromEntries, Monoid

#Construction

#singleton

singleton : a -> Set a
singleton x

A set with one element.

> size (singleton 5)
1

#fromList

fromList : Ord a => List a -> Set a
fromList xs

A set holding the elements of a list, without duplicates.

The Set { x, ... } literal is the same operation.

> toList (fromList [3, 1, 2, 3, 1])
[1, 2, 3]

#Query

#size

size : Set a -> Int

The number of elements, in O(1).

> size (fromList [1, 2, 3, 2])
3

#has

has : Ord a => a -> Set a -> Bool
has x _

Whether x is a member.

> has 2 (fromList [1, 2, 3])
True
> has 9 (fromList [1, 2, 3])
False

#Insertion and deletion

#insert

insert : Ord a => a -> Set a -> Set a
insert x _

The set with x added.

Unchanged when x is already a member.

> size (insert 9 (fromList [1, 2, 3]))
4

#delete

delete : Ord a => a -> Set a -> Set a
delete x _

The set without x.

Unchanged when x is not a member.

> has 2 (delete 2 (fromList [1, 2, 3]))
False

#Minimum and maximum

#minView

minView : Set a -> Option (a, Set a)

The smallest element and the set without it, or None when the set is empty.

> minView (fromList [2, 1, 3])
Some (1, fromList [2, 3])

#maxView

maxView : Set a -> Option (a, Set a)

The largest element and the set without it, or None when the set is empty.

> maxView (fromList [2, 1, 3])
Some (3, fromList [1, 2])

#getMin

getMin : Set a -> Option a
getMin s

The smallest element, or None when the set is empty.

> getMin (fromList [3, 1, 2])
Some 1

#getMax

getMax : Set a -> Option a
getMax s

The largest element, or None when the set is empty.

> getMax (fromList [3, 1, 2])
Some 3

#deleteMin

deleteMin : Set a -> Set a
deleteMin s

The set without its smallest element.

Unchanged when the set is empty.

> toList (deleteMin (fromList [3, 1, 2]))
[2, 3]

#deleteMax

deleteMax : Set a -> Set a
deleteMax s

The set without its largest element.

Unchanged when the set is empty.

> toList (deleteMax (fromList [3, 1, 2]))
[1, 2]

#Set algebra

#union

union : Ord a => Set a -> Set a -> Set a
union a b

The elements in either set.

++ on sets is union.

> toList (union (fromList [1, 2]) (fromList [2, 3]))
[1, 2, 3]

#intersection

intersection : Ord a => Set a -> Set a -> Set a
intersection a b

The elements in both sets.

> toList (intersection (fromList [1, 2, 3]) (fromList [2, 3, 4]))
[2, 3]

#difference

difference : Ord a => Set a -> Set a -> Set a
difference a b

The elements of the first set that are not in the second.

> toList (difference (fromList [1, 2, 3]) (fromList [2]))
[1, 3]

#isSubsetOf

isSubsetOf : Ord a => Set a -> Set a -> Bool
isSubsetOf a b

Whether every element of the first set is in the second.

> isSubsetOf (fromList [1, 2]) (fromList [1, 2, 3])
True
> isSubsetOf (fromList [1, 4]) (fromList [1, 2, 3])
False

#Invariants

#wellFormed

wellFormed : Ord a => Set a -> Bool

Whether the set's internal tree satisfies its invariants: elements in search order, correct cached sizes, and balanced subtrees.

Every set built with this module's functions is well formed. This is a debugging aid and the basis of the module's property tests.

> wellFormed (fromList [5, 3, 8, 1, 4, 7, 9, 2, 6])
True

#Instances

#Foldable Set

impl Foldable Set

The Foldable methods visit elements in ascending order, so toList, length, elem, sum, maximum, any, and all work on a set.

> toList (fromList [3, 1, 2, 1])
[1, 2, 3]
> length (fromList [3, 1, 2, 1])
3

#Eq (Set a)

impl Eq (Set a) requires Eq a

Two sets are equal when they hold the same elements, regardless of how they were built.

> eq (fromList [1, 2, 3]) (fromList [3, 2, 1, 2])
True

#Ord (Set a)

impl Ord (Set a) requires Ord a

Sets compare lexicographically by their ascending element lists.

> compare (fromList [1, 2]) (fromList [1, 3])
Lt

#Debug (Set a)

impl Debug (Set a) requires Debug a

debug renders a set as fromList [x, ...].

> debug (fromList [1, 2, 3])
"fromList [1, 2, 3]"

#Display (Set a)

impl Display (Set a) requires Display a

display renders a set in its literal syntax, Set { x, ... }.

> display (fromList [1, 2, 3])
"Set { 1, 2, 3 }"
> display (empty : Set Int)
"Set {}"

#Semigroup (Set a)

impl Semigroup (Set a) requires Ord a

++ on sets is union.

#FromEntries (Set a) a

impl FromEntries (Set a) a requires Ord a

The Set { x, ... } literal builds its set through this instance.

#Monoid (Set a)

impl Monoid (Set a) requires Ord a

The set with no elements.

> isEmpty (empty : Set Int)
True