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

Safe HaskellSafe
LanguageHaskell2010

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
Functor Deque Source # 
Instance details

Defined in Data.CompactSequence.Deque.Simple.Internal

Methods

fmap :: (a -> b) -> Deque a -> Deque b #

(<$) :: a -> Deque b -> Deque a #

Foldable Deque Source # 
Instance details

Defined in Data.CompactSequence.Deque.Simple.Internal

Methods

fold :: 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 #

Traversable Deque Source # 
Instance details

Defined in Data.CompactSequence.Deque.Simple.Internal

Methods

traverse :: 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

Defined in Data.CompactSequence.Deque.Simple.Internal

Associated Types

type Item (Deque a) :: Type #

Methods

fromList :: [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

Defined in Data.CompactSequence.Deque.Simple.Internal

Methods

(==) :: Deque a -> Deque a -> Bool #

(/=) :: Deque a -> Deque a -> Bool #

Ord a => Ord (Deque a) Source # 
Instance details

Defined in Data.CompactSequence.Deque.Simple.Internal

Methods

compare :: 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

Defined in Data.CompactSequence.Deque.Simple.Internal

Methods

showsPrec :: Int -> Deque a -> ShowS #

show :: Deque a -> String #

showList :: [Deque a] -> ShowS #

Semigroup (Deque a) Source # 
Instance details

Defined in Data.CompactSequence.Deque.Simple.Internal

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

Defined in Data.CompactSequence.Deque.Simple.Internal

Methods

mempty :: Deque a #

mappend :: Deque a -> Deque a -> Deque a #

mconcat :: [Deque a] -> Deque a #

type Item (Deque a) Source # 
Instance details

Defined in Data.CompactSequence.Deque.Simple.Internal

type Item (Deque a) = a

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

An infix synonym for snoc.

empty :: Deque a Source #

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.