Control.Monad.Constrained.IntSet

This module creates an IntSet type with a phantom type variable, allowing it to conform to Functor, Foldable, etc. Other than that, it's a duplication of the Data.IntSet module.

IntSet type

data IntSet a

This type is a wrapper around IntSet, with a phantom type variable which must always be Int. This allows it to conform to Functor, Foldable, Applicative, Monad, etc.

Instances

Foldable IntSet

Methods

fold :: Monoid m => IntSet m -> m

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

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

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

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

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

foldr1 :: (a -> a -> a) -> IntSet a -> a

foldl1 :: (a -> a -> a) -> IntSet a -> a

toList :: IntSet a -> [a]

null :: IntSet a -> Bool

length :: IntSet a -> Int

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

maximum :: Ord a => IntSet a -> a

minimum :: Ord a => IntSet a -> a

sum :: Num a => IntSet a -> a

product :: Num a => IntSet a -> a

Eq1 IntSet

Methods

liftEq :: (a -> b -> Bool) -> IntSet a -> IntSet b -> Bool

Ord1 IntSet

Methods

liftCompare :: (a -> b -> Ordering) -> IntSet a -> IntSet b -> Ordering

Show1 IntSet

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> IntSet a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [IntSet a] -> ShowS

Alternative IntSet

Methods

empty :: Suitable IntSet a => IntSet a

(<|>) :: Suitable IntSet a => IntSet a -> IntSet a -> IntSet a

some :: Suitable IntSet [a] => IntSet a -> IntSet [a]

many :: Suitable IntSet [a] => IntSet a -> IntSet [a]

Monad IntSet

Methods

(>>=) :: Suitable IntSet b => IntSet a -> (a -> IntSet b) -> IntSet b

Applicative IntSet

Associated Types

type Unconstrained (IntSet :: * -> *) :: * -> *

Methods

reflect :: IntSet a -> Unconstrained IntSet a

reify :: Suitable IntSet a => Unconstrained IntSet a -> IntSet a

pure :: Suitable IntSet a => a -> IntSet a

(<*>) :: Suitable IntSet b => IntSet (a -> b) -> IntSet a -> IntSet b

(*>) :: Suitable IntSet b => IntSet a -> IntSet b -> IntSet b

(<*) :: Suitable IntSet a => IntSet a -> IntSet b -> IntSet a

liftA2 :: Suitable IntSet c => (a -> b -> c) -> IntSet a -> IntSet b -> IntSet c

liftA3 :: Suitable IntSet d => (a -> b -> c -> d) -> IntSet a -> IntSet b -> IntSet c -> IntSet d

Functor IntSet

Associated Types

type Suitable (IntSet :: * -> *) a :: Constraint

Methods

fmap :: Suitable IntSet b => (a -> b) -> IntSet a -> IntSet b

(<$) :: Suitable IntSet a => a -> IntSet b -> IntSet a

(~) * a Int => IsList (IntSet a)

Associated Types

type Item (IntSet a) :: *

Methods

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

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

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

Eq a => Eq (IntSet a)

Methods

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

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

(~) * a Int => Data (IntSet a)

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> IntSet a -> c (IntSet a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (IntSet a)

toConstr :: IntSet a -> Constr

dataTypeOf :: IntSet a -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c (IntSet a))

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (IntSet a))

gmapT :: (forall b. Data b => b -> b) -> IntSet a -> IntSet a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> IntSet a -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> IntSet a -> r

gmapQ :: (forall d. Data d => d -> u) -> IntSet a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> IntSet a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> IntSet a -> m (IntSet a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> IntSet a -> m (IntSet a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> IntSet a -> m (IntSet a)

Ord a => Ord (IntSet a)

Methods

compare :: IntSet a -> IntSet a -> Ordering

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

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

(>) :: IntSet a -> IntSet a -> Bool

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

max :: IntSet a -> IntSet a -> IntSet a

min :: IntSet a -> IntSet a -> IntSet a

(~) * a Int => Read (IntSet a)

Methods

readsPrec :: Int -> ReadS (IntSet a)

readList :: ReadS [IntSet a]

readPrec :: ReadPrec (IntSet a)

readListPrec :: ReadPrec [IntSet a]

Show a => Show (IntSet a)

Methods

showsPrec :: Int -> IntSet a -> ShowS

show :: IntSet a -> String

showList :: [IntSet a] -> ShowS

Semigroup (IntSet a)

Methods

(<>) :: IntSet a -> IntSet a -> IntSet a

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

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

(~) * a Int => Monoid (IntSet a)

Methods

mempty :: IntSet a

mappend :: IntSet a -> IntSet a -> IntSet a

mconcat :: [IntSet a] -> IntSet a

NFData (IntSet a)

Methods

rnf :: IntSet a -> ()

type Unconstrained IntSet

type Unconstrained IntSet

type Suitable IntSet a

type Suitable IntSet a = (~) * a Int

type Item (IntSet a)

type Item (IntSet a) = a

Operators

(\\) :: IntSet a -> IntSet a -> IntSet a infixl 9

O(n+m). See difference.

Query

lookupLT :: a -> IntSet a -> Maybe a

O(log n). Find largest element smaller than the given one.

lookupLT 3 (fromList [3, 5]) == Nothing
lookupLT 5 (fromList [3, 5]) == Just 3

lookupLE :: a -> IntSet a -> Maybe a

O(log n). Find largest element smaller or equal to the given one.

lookupLE 2 (fromList [3, 5]) == Nothing
lookupLE 4 (fromList [3, 5]) == Just 3
lookupLE 5 (fromList [3, 5]) == Just 5

lookupGT :: a -> IntSet a -> Maybe a

O(log n). Find smallest element greater than the given one.

lookupGT 4 (fromList [3, 5]) == Just 5
lookupGT 5 (fromList [3, 5]) == Nothing

lookupGE :: a -> IntSet a -> Maybe a

O(log n). Find smallest element greater or equal to the given one.

lookupGE 3 (fromList [3, 5]) == Just 3
lookupGE 4 (fromList [3, 5]) == Just 5
lookupGE 6 (fromList [3, 5]) == Nothing

isSubsetOf :: IntSet a -> IntSet a -> Bool

isProperSubsetOf :: IntSet a -> IntSet a -> Bool

Construction

insert :: a -> IntSet a -> IntSet a

O(min(n,W)). Add a value to the set. There is no left- or right bias for IntSets.

delete :: a -> IntSet a -> IntSet a

O(min(n,W)). Delete a value in the set. Returns the original set when the value was not present.

Combine

difference :: IntSet a -> IntSet a -> IntSet a

O(n+m). Difference between two sets.

intersection :: IntSet a -> IntSet a -> IntSet a

O(n+m). The intersection of two sets.

Filter

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

O(n). Filter all elements that satisfy some predicate.

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

O(n). partition the set according to some predicate.

split :: a -> IntSet a -> (IntSet a, IntSet a)

O(min(n,W)). The expression (split x set) is a pair (set1,set2) where set1 comprises the elements of set less than x and set2 comprises the elements of set greater than x.

split 3 (fromList [1..5]) == (fromList [1,2], fromList [4,5])

splitMember :: a -> IntSet a -> (IntSet a, Bool, IntSet a)

splitRoot :: IntSet a -> [IntSet a]

Min/Max

maxView :: IntSet a -> Maybe (a, IntSet a)

O(min(n,W)). Retrieves the maximal key of the set, and the set stripped of that element, or Nothing if passed an empty set.

minView :: IntSet a -> Maybe (a, IntSet a)

O(min(n,W)). Retrieves the minimal key of the set, and the set stripped of that element, or Nothing if passed an empty set.

deleteMin :: IntSet a -> IntSet a

deleteMax :: IntSet a -> IntSet a

Ordered List

toAscList :: IntSet a -> [a]

toDescList :: IntSet a -> [a]

fromAscList :: [Int] -> IntSet Int

fromDistinctAscList :: [Int] -> IntSet Int