Copyright	(C) 2012-15 Edward Kmett
License	BSD-style (see the file LICENSE)
Maintainer	Edward Kmett <ekmett@gmail.com>
Stability	experimental
Portability	non-portable
Safe Haskell	Safe
Language	Haskell98

Control.Lens.Internal.Deque

Description

This module is designed to be imported qualified.

Synopsis

Documentation

data Deque a Source

A Banker's deque based on Chris Okasaki's "Purely Functional Data Structures"

Constructors

BD !Int [a] !Int [a]

Instances

Monad Deque
Methods (>>=) :: Deque a -> (a -> Deque b) -> Deque b (>>) :: Deque a -> Deque b -> Deque b return :: a -> Deque a fail :: String -> Deque a
Functor Deque
Methods fmap :: (a -> b) -> Deque a -> Deque b (<$) :: a -> Deque b -> Deque a
Applicative Deque
Methods pure :: a -> Deque a (<>) :: Deque (a -> b) -> Deque a -> Deque b (>) :: Deque a -> Deque b -> Deque b (<*) :: Deque a -> Deque b -> Deque a
Foldable Deque
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
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)
Alternative Deque
Methods empty :: Deque a (<\|>) :: Deque a -> Deque a -> Deque a some :: Deque a -> Deque [a] many :: Deque a -> Deque [a]
MonadPlus Deque
Methods mzero :: Deque a mplus :: Deque a -> Deque a -> Deque a
Plus Deque
Methods zero :: Deque a
Alt Deque
Methods (<!>) :: Deque a -> Deque a -> Deque a some :: Applicative Deque => Deque a -> Deque [a] many :: Applicative Deque => Deque a -> Deque [a]
Apply Deque
Methods (<.>) :: Deque (a -> b) -> Deque a -> Deque b (.>) :: Deque a -> Deque b -> Deque b (<.) :: Deque a -> Deque b -> Deque a
Bind Deque
Methods (>>-) :: Deque a -> (a -> Deque b) -> Deque b join :: Deque (Deque a) -> Deque a
TraversableWithIndex Int Deque
Methods itraverse :: Applicative f => (Int -> a -> f b) -> Deque a -> f (Deque b) Source itraversed :: (Indexable Int p, Applicative f) => p a (f b) -> Deque a -> f (Deque b) Source
FoldableWithIndex Int Deque
Methods ifoldMap :: Monoid m => (Int -> a -> m) -> Deque a -> m Source ifolded :: (Indexable Int p, Contravariant f, Applicative f) => p a (f a) -> Deque a -> f (Deque a) Source ifoldr :: (Int -> a -> b -> b) -> b -> Deque a -> b Source ifoldl :: (Int -> b -> a -> b) -> b -> Deque a -> b Source ifoldr' :: (Int -> a -> b -> b) -> b -> Deque a -> b Source ifoldl' :: (Int -> b -> a -> b) -> b -> Deque a -> b Source
FunctorWithIndex Int Deque
Methods imap :: (Int -> a -> b) -> Deque a -> Deque b Source imapped :: (Indexable Int p, Settable f) => p a (f b) -> Deque a -> f (Deque b) Source
Eq a => Eq (Deque a)
Methods (==) :: Deque a -> Deque a -> Bool (/=) :: Deque a -> Deque a -> Bool
Ord a => Ord (Deque a)
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)
Methods showsPrec :: Int -> Deque a -> ShowS show :: Deque a -> String showList :: [Deque a] -> ShowS
Monoid (Deque a)
Methods mempty :: Deque a mappend :: Deque a -> Deque a -> Deque a mconcat :: [Deque a] -> Deque a
Semigroup (Deque a)
Methods (<>) :: Deque a -> Deque a -> Deque a sconcat :: NonEmpty (Deque a) -> Deque a times1p :: Natural -> Deque a -> Deque a
Reversing (Deque a)
Methods reversing :: Deque a -> Deque a Source
Snoc (Deque a) (Deque b) a b
Methods _Snoc :: Prism (Deque a) (Deque b) (Deque a, a) (Deque b, b) Source
Cons (Deque a) (Deque b) a b
Methods _Cons :: Prism (Deque a) (Deque b) (a, Deque a) (b, Deque b) Source

size :: Deque a -> Int Source

O(1). Calculate the size of a Deque

>>> size (fromList [1,4,6])
3

fromList :: [a] -> Deque a Source

O(n) amortized. Construct a Deque from a list of values.

>>> fromList [1,2]
BD 1 [1] 1 [2]

null :: Deque a -> Bool Source

O(1). Determine if a Deque is empty.

>>> null empty
True

>>> null (singleton 1)
False

singleton :: a -> Deque a Source

O(1). Generate a singleton Deque

>>> singleton 1
BD 1 [1] 0 []