Mini.Data.Set

Representation of a structure containing unique elements. The internal structure is an AVL tree.

Type

data Set a

A set containing elements of type a.

The internal structure is an AVL tree; a tree that is always height-balanced (the absolute value of the level difference between the left and right subtrees is at most 1).

Instances

Foldable Set

Defined in Mini.Data.Set

Methods

fold :: Monoid m => Set m -> m

foldMap :: Monoid m => (a -> m) -> Set a -> m

foldMap' :: Monoid m => (a -> m) -> Set a -> m

foldr :: (a -> b -> b) -> b -> Set a -> b

foldr' :: (a -> b -> b) -> b -> Set a -> b

foldl :: (b -> a -> b) -> b -> Set a -> b

foldl' :: (b -> a -> b) -> b -> Set a -> b

foldr1 :: (a -> a -> a) -> Set a -> a

foldl1 :: (a -> a -> a) -> Set a -> a

toList :: Set a -> [a]

null :: Set a -> Bool

length :: Set a -> Int

elem :: Eq a => a -> Set a -> Bool

maximum :: Ord a => Set a -> a

minimum :: Ord a => Set a -> a

sum :: Num a => Set a -> a

product :: Num a => Set a -> a

Show a => Show (Set a)

Defined in Mini.Data.Set

Methods

showsPrec :: Int -> Set a -> ShowS

show :: Set a -> String

showList :: [Set a] -> ShowS

Eq a => Eq (Set a)

Defined in Mini.Data.Set

Methods

(==) :: Set a -> Set a -> Bool

(/=) :: Set a -> Set a -> Bool

Ord a => Ord (Set a)

Defined in Mini.Data.Set

Methods

compare :: Set a -> Set a -> Ordering

(<) :: Set a -> Set a -> Bool

(<=) :: Set a -> Set a -> Bool

(>) :: Set a -> Set a -> Bool

(>=) :: Set a -> Set a -> Bool

max :: Set a -> Set a -> Set a

min :: Set a -> Set a -> Set a

Combination

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

\(O(n \log n)\) Set difference

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

\(O(n \log n)\) Set intersection

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

\(O(n \log n)\) Set union

Construction

empty :: Set a

\(O(1)\) The empty set

fromList :: Ord a => [a] -> Set a

\(O(n \log n)\) From a tail-biased list of elements to a set containing the elements

singleton :: a -> Set a

\(O(1)\) From an element to a set with a single element

Conversion

toAscList :: Set a -> [a]

\(O(n)\) From a set to a list of elements in ascending order

toDescList :: Set a -> [a]

\(O(n)\) From a set to a list of elements in descending order

Modification

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

\(O(\log n)\) From an element and a set to the set without the element

filter :: Ord a => (a -> Bool) -> Set a -> Set a

\(O(n)\) From a predicate and a set to the set with elements satisfying the predicate

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

\(O(\log n)\) From an element and a set to the set including the element

Query

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

\(O(n \log n)\) From a set and another set to whether the former is a subset of the latter

lookupMax :: Set a -> Maybe a

\(O(\log n)\) From a set to the maximum element of the set

lookupMin :: Set a -> Maybe a

\(O(\log n)\) From a set to the minimum element of the set

member :: Ord a => a -> Set a -> Bool

\(O(\log n)\) From an element and a set to whether the element is in the set

null :: Set a -> Bool

\(O(1)\) From a set to whether the set is empty

size :: Set a -> Int

\(O(n)\) From a set to the size of the set

Validation

valid :: Ord a => Set a -> Bool

\(O(n)\) From a set to whether its internal structure is valid, i.e. height-balanced and ordered