compact-sequences-0.1.0.0: Stacks and queues with compact representations.

Data.CompactSequence.Queue.Simple

Description

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.

Synopsis

# Documentation

data Queue a where Source #

Bundled Patterns

 pattern Empty :: Queue a pattern (:<) :: a -> Queue a -> Queue a infixr 4
Instances
 Source # Instance detailsDefined in Data.CompactSequence.Queue.Simple Methodsfmap :: (a -> b) -> Queue a -> Queue b #(<\$) :: a -> Queue b -> Queue a # Source # Instance detailsDefined in Data.CompactSequence.Queue.Simple Methodsfold :: 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 # Source # Instance detailsDefined in Data.CompactSequence.Queue.Simple Methodstraverse :: 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) Source # Instance detailsDefined in Data.CompactSequence.Queue.Simple Associated Typestype Item (Queue a) :: Type # MethodsfromList :: [Item (Queue a)] -> Queue a #fromListN :: Int -> [Item (Queue a)] -> Queue a #toList :: Queue a -> [Item (Queue a)] # Eq a => Eq (Queue a) Source # Instance detailsDefined in Data.CompactSequence.Queue.Simple Methods(==) :: Queue a -> Queue a -> Bool #(/=) :: Queue a -> Queue a -> Bool # Ord a => Ord (Queue a) Source # Instance detailsDefined in Data.CompactSequence.Queue.Simple Methodscompare :: 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) Source # Instance detailsDefined in Data.CompactSequence.Queue.Simple MethodsshowsPrec :: Int -> Queue a -> ShowS #show :: Queue a -> String #showList :: [Queue a] -> ShowS # Source # Instance detailsDefined 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) Source # Instance detailsDefined in Data.CompactSequence.Queue.Simple Methodsmempty :: Queue a #mappend :: Queue a -> Queue a -> Queue a #mconcat :: [Queue a] -> Queue a # type Item (Queue a) Source # Instance detailsDefined in Data.CompactSequence.Queue.Simple type Item (Queue a) = a

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

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

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

fromList :: [a] -> Queue a Source #

$$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 Source #

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