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

Primitive Recursion

set

Arguments

:: b

Value yielded in case of empty node

-> (Set a -> a -> Set a -> b -> b -> b)

Function applied in case of non-empty node: left child, element, right child, left recursion, right recursion (elements are lesser to the left, greater to the right)

-> Set a

Object of the case analysis

-> b

Primitive recursion on sets (internally structured as trees)

Construction

empty :: Set a

O(1) The empty set

singleton :: a -> Set a

O(1) Make a set with a single element

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

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

fromAscList :: Eq a => [a] -> Set a

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

fromDescList :: Eq a => [a] -> Set a

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

fromDistinctAscList :: [a] -> Set a

O(n) Make a set from a sorted list of distinct elements

fromDistinctDescList :: [a] -> Set a

O(n) Make a set from a sorted list of distinct elements

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

unions :: (Foldable t, Ord a) => t (Set a) -> Set a

Unite a collection of sets

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

deleteMax :: Ord a => Set a -> Set a

O(log n) Delete the maximum element from a set

deleteMin :: Ord a => Set a -> Set a

O(log n) Delete the minimum element from a set

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

O(n) Keep the elements satisfying a predicate

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

O(log n) Insert an element into a set

Partition

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

O(n) Partition a set with a predicate into (true, false) subsets

split :: Ord a => a -> Set a -> (Set a, Bool, Set a)

O(n) Split a set by an element into (lt, eq, gt) subsets

splitMax :: Ord a => Set a -> Maybe (a, Set a)

O(log n) Split a set by its maximum element

splitMin :: Ord a => Set a -> Maybe (a, Set a)

O(log n) Split a set by its minimum element

Query

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

O(m log n) Check whether two sets have no elements in common

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^2) Check whether a set is internally height-balanced and ordered