Data.Diet.Set.Lifted

Documentation

data Set a

Instances

(Ord a, Enum a) => IsList (Set a)

Associated Types

type Item (Set a) :: *

Methods

fromList :: [Item (Set a)] -> Set a

fromListN :: Int -> [Item (Set a)] -> Set a

toList :: Set a -> [Item (Set a)]

Eq a => Eq (Set a)

Methods

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

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

Ord a => Ord (Set a)

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

Show a => Show (Set a)

Methods

showsPrec :: Int -> Set a -> ShowS

show :: Set a -> String

showList :: [Set a] -> ShowS

(Ord a, Enum a) => Semigroup (Set a)

Methods

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

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

stimes :: Integral b => b -> Set a -> Set a

(Ord a, Enum a) => Monoid (Set a)

Methods

mempty :: Set a

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

mconcat :: [Set a] -> Set a

type Item (Set a)

type Item (Set a) = (a, a)

singleton

Arguments

:: Ord a

=> a

inclusive lower bound

-> a

inclusive upper bound

-> Set a

O(1) Create a diet set with a single element.

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

O(log n) Lookup the value at a key in the map.

difference

Arguments

:: (Ord a, Enum a)

=> Set a

minuend

-> Set a

subtrahend

-> Set a

O(n + m*log n) Subtract the subtrahend of size m from the minuend of size n. It should be possible to improve the improve the performance of this to O(n + m). Anyone interested in doing this should open a PR.

Split

aboveInclusive

Arguments

:: Ord a

=> a

inclusive lower bound

-> Set a

-> Set a

O(n) The subset where all elements are greater than or equal to the given value.

belowInclusive

Arguments

:: Ord a

=> a

inclusive upper bound

-> Set a

-> Set a

O(n) The subset where all elements are less than or equal to the given value.

betweenInclusive

Arguments

:: Ord a

=> a

inclusive lower bound

-> a

inclusive upper bound

-> Set a

-> Set a

O(n) The subset where all elements are greater than or equal to the lower bound and less than or equal to the upper bound.

Folds

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

List Conversion

fromList :: (Ord a, Enum a) => [(a, a)] -> Set a

fromListN

Arguments

:: (Ord a, Enum a)

=> Int

expected size of resulting diet Set

-> [(a, a)]

key-value pairs

-> Set a