Safe Haskell	Trustworthy
Language	Haskell2010

Data.CompactSequence.Deque.Simple.Internal

Description

Space-efficient deques 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 deque.

Synopsis

newtype Deque a where
- Deque (Deque Sz1 a)
- pattern Empty :: Deque a
- pattern (:<) :: a -> Deque a -> Deque a
- pattern (:>) :: Deque a -> a -> Deque a
(|>) :: Deque a -> a -> Deque a
(<|) :: a -> Deque a -> Deque a
empty :: Deque a
cons :: a -> Deque a -> Deque a
snoc :: Deque a -> a -> Deque a
uncons :: Deque a -> Maybe (a, Deque a)
unsnoc :: Deque a -> Maybe (Deque a, a)
fromList :: [a] -> Deque a
fromListN :: Int -> [a] -> Deque a

Documentation

newtype Deque a Source #

A deque.

Constructors

Deque (Deque Sz1 a)

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.

(<|) :: a -> Deque a -> Deque a Source #

An infix synonym for cons.

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.