Data.CompactSequence.Queue.Simple

Space-efficient queues with amortized \( O(\log n) \) operations. These directly use an underlying array-based implementation, without doing any special optimization for the first few and last few elements of the queue.

Documentation

data Queue a where

Bundled Patterns

pattern Empty :: Queue a

pattern (:<) :: a -> Queue a -> Queue a infixr 4

Instances

Functor Queue

Defined in Data.CompactSequence.Queue.Simple

Methods

fmap :: (a -> b) -> Queue a -> Queue b

(<$) :: a -> Queue b -> Queue a

Foldable Queue

Defined in Data.CompactSequence.Queue.Simple

Methods

fold :: Monoid m => Queue m -> m

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

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

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

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

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

foldr1 :: (a -> a -> a) -> Queue a -> a

foldl1 :: (a -> a -> a) -> Queue a -> a

toList :: Queue a -> [a]

null :: Queue a -> Bool

length :: Queue a -> Int

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

maximum :: Ord a => Queue a -> a

minimum :: Ord a => Queue a -> a

sum :: Num a => Queue a -> a

product :: Num a => Queue a -> a

Traversable Queue

Defined in Data.CompactSequence.Queue.Simple

Methods

traverse :: Applicative f => (a -> f b) -> Queue a -> f (Queue b)

sequenceA :: Applicative f => Queue (f a) -> f (Queue a)

mapM :: Monad m => (a -> m b) -> Queue a -> m (Queue b)

sequence :: Monad m => Queue (m a) -> m (Queue a)

IsList (Queue a)

Defined in Data.CompactSequence.Queue.Simple

Associated Types

type Item (Queue a) :: Type

Methods

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

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

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

Eq a => Eq (Queue a)

Defined in Data.CompactSequence.Queue.Simple

Methods

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

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

Ord a => Ord (Queue a)

Defined in Data.CompactSequence.Queue.Simple

Methods

compare :: Queue a -> Queue a -> Ordering

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

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

(>) :: Queue a -> Queue a -> Bool

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

max :: Queue a -> Queue a -> Queue a

min :: Queue a -> Queue a -> Queue a

Show a => Show (Queue a)

Defined in Data.CompactSequence.Queue.Simple

Methods

showsPrec :: Int -> Queue a -> ShowS

show :: Queue a -> String

showList :: [Queue a] -> ShowS

Semigroup (Queue a)

Defined in Data.CompactSequence.Queue.Simple

Methods

(<>) :: Queue a -> Queue a -> Queue a

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

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

Monoid (Queue a)

Defined in Data.CompactSequence.Queue.Simple

Methods

mempty :: Queue a

mappend :: Queue a -> Queue a -> Queue a

mconcat :: [Queue a] -> Queue a

type Item (Queue a)

Defined in Data.CompactSequence.Queue.Simple

type Item (Queue a) = a

(|>) :: Queue a -> a -> Queue a

empty :: Queue a

snoc :: Queue a -> a -> Queue a infixl 4

uncons :: Queue a -> Maybe (a, Queue a)

fromList :: [a] -> Queue a

\( O(n \log n) \). Convert a list to a Queue, with the head of the list at the front of the queue.

fromListN :: Int -> [a] -> Queue a

\( O(n) \). Convert a list of the given size to a Queue, with the head of the list at the front of the queue.