compact-sequences-0.2.0.0: Stacks, queues, and deques with compact representations.

Data.CompactSequence.Deque.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 Deque a where Source #

A deque.

Bundled Patterns

 pattern Empty :: Deque a A bidirectional pattern synonym for the empty deque. pattern (:<) :: a -> Deque a -> Deque a infixr 5 A bidirectional pattern synonym for manipulating the front of a deque. pattern (:>) :: Deque a -> a -> Deque a A bidirectional pattern synonym for manipulating the rear of a deque.
Instances
 Source # Instance details Methodsfmap :: (a -> b) -> Deque a -> Deque b #(<\$) :: a -> Deque b -> Deque a # Source # Instance details Methodsfold :: Monoid m => Deque m -> m #foldMap :: Monoid m => (a -> m) -> Deque a -> m #foldr :: (a -> b -> b) -> b -> Deque a -> b #foldr' :: (a -> b -> b) -> b -> Deque a -> b #foldl :: (b -> a -> b) -> b -> Deque a -> b #foldl' :: (b -> a -> b) -> b -> Deque a -> b #foldr1 :: (a -> a -> a) -> Deque a -> a #foldl1 :: (a -> a -> a) -> Deque a -> a #toList :: Deque a -> [a] #null :: Deque a -> Bool #length :: Deque a -> Int #elem :: Eq a => a -> Deque a -> Bool #maximum :: Ord a => Deque a -> a #minimum :: Ord a => Deque a -> a #sum :: Num a => Deque a -> a #product :: Num a => Deque a -> a # Source # Instance details Methodstraverse :: Applicative f => (a -> f b) -> Deque a -> f (Deque b) #sequenceA :: Applicative f => Deque (f a) -> f (Deque a) #mapM :: Monad m => (a -> m b) -> Deque a -> m (Deque b) #sequence :: Monad m => Deque (m a) -> m (Deque a) # IsList (Deque a) Source # Instance details Associated Typestype Item (Deque a) :: Type # MethodsfromList :: [Item (Deque a)] -> Deque a #fromListN :: Int -> [Item (Deque a)] -> Deque a #toList :: Deque a -> [Item (Deque a)] # Eq a => Eq (Deque a) Source # Instance details Methods(==) :: Deque a -> Deque a -> Bool #(/=) :: Deque a -> Deque a -> Bool # Ord a => Ord (Deque a) Source # Instance details Methodscompare :: Deque a -> Deque a -> Ordering #(<) :: Deque a -> Deque a -> Bool #(<=) :: Deque a -> Deque a -> Bool #(>) :: Deque a -> Deque a -> Bool #(>=) :: Deque a -> Deque a -> Bool #max :: Deque a -> Deque a -> Deque a #min :: Deque a -> Deque a -> Deque a # Show a => Show (Deque a) Source # Instance details MethodsshowsPrec :: Int -> Deque a -> ShowS #show :: Deque a -> String #showList :: [Deque a] -> ShowS # Source # Instance details Methods(<>) :: Deque a -> Deque a -> Deque a #sconcat :: NonEmpty (Deque a) -> Deque a #stimes :: Integral b => b -> Deque a -> Deque a # Monoid (Deque a) Source # Instance details Methodsmempty :: Deque a #mappend :: Deque a -> Deque a -> Deque a #mconcat :: [Deque a] -> Deque a # type Item (Deque a) Source # Instance details type Item (Deque a) = a

(|>) :: Deque a -> a -> Deque a infixl 4 Source #

An infix synonym for snoc.

The empty deque.

cons :: a -> Deque a -> Deque a infixr 5 Source #

Enqueue an element at the front of a deque.

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

Enqueue an element at the rear of a deque.

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

Dequeue an element from the front of a deque.

unsnoc :: Deque a -> Maybe (Deque a, a) Source #

Dequeue an element from the rear of a deque.

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

$$O(n \log n)$$. Convert a list to a Deque, with the head of the list at the front of the deque.

fromListN :: Int -> [a] -> Deque a Source #

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