Mini.Data.Set

A structure containing unique elements

Type

data Set a

A set containing elements of type a, internally structured as an AVL tree

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

Ord a => Monoid (Set a)

Defined in Mini.Data.Set

Methods

mempty :: Set a

mappend :: Set a -> Set a -> Set a

mconcat :: [Set a] -> Set a

Ord a => Semigroup (Set a)

Defined in Mini.Data.Set

Methods

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

sconcat :: NonEmpty (Set a) -> Set a

stimes :: Integral b => b -> Set a -> Set 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

Construction

empty :: Set a

O(1) The empty set

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

O(n log n) Make a set from a list of elements

singleton :: a -> Set a

O(1) Make a set with a single element

Combination

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

O(m log n) Subtract a set by another

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

O(m log n) Intersect a set with another

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

O(m log n) Unite a set with another

Conversion

toAscList :: Set a -> [a]

O(n) Turn a set into a list of elements in ascending order

toDescList :: Set a -> [a]

O(n) Turn a set into a list of elements in descending order

Modification

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

O(log n) Delete an element from a set

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

O(n log n) Keep the elements satisfying a predicate

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

O(log n) Insert an element into a set

Query

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

O(n log m) Check whether the elements of a set exist in the other

lookupGE :: Ord a => a -> Set a -> Maybe a

O(log n) Fetch the least element greater than or equal to the given one

lookupGT :: Ord a => a -> Set a -> Maybe a

O(log n) Fetch the least element strictly greater than the given one

lookupLE :: Ord a => a -> Set a -> Maybe a

O(log n) Fetch the greatest element less than or equal to the given one

lookupLT :: Ord a => a -> Set a -> Maybe a

O(log n) Fetch the greatest element strictly less than the given one

lookupMax :: Set a -> Maybe a

O(log n) Fetch the maximum element, or Nothing if the set is empty

lookupMin :: Set a -> Maybe a

O(log n) Fetch the minimum element, or Nothing if the set is empty

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

O(log n) Check whether an element is in a set

null :: Set a -> Bool

O(1) Check whether a set is empty

size :: Set a -> Int

O(n) Get the size of a set

Validation

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

O(n) Check whether a set is internally height-balanced and ordered