Copyright	(C) 2012-16 Edward Kmett
License	BSD-style (see the file LICENSE)
Maintainer	Edward Kmett <[email protected]>
Stability	experimental
Portability	non-portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

Control.Lens.Internal.Deque

Description

This module is designed to be imported qualified.

Synopsis

data Deque a = BD !Int [a] !Int [a]
size :: Deque a -> Int
fromList :: [a] -> Deque a
null :: Deque a -> Bool
singleton :: a -> Deque a

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

Instances details

Foldable Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods fold :: Monoid m => Deque m -> m Source # foldMap :: Monoid m => (a -> m) -> Deque a -> m Source # foldMap' :: Monoid m => (a -> m) -> Deque a -> m Source # foldr :: (a -> b -> b) -> b -> Deque a -> b Source # foldr' :: (a -> b -> b) -> b -> Deque a -> b Source # foldl :: (b -> a -> b) -> b -> Deque a -> b Source # foldl' :: (b -> a -> b) -> b -> Deque a -> b Source # foldr1 :: (a -> a -> a) -> Deque a -> a Source # foldl1 :: (a -> a -> a) -> Deque a -> a Source # toList :: Deque a -> [a] Source # null :: Deque a -> Bool Source # length :: Deque a -> Int Source # elem :: Eq a => a -> Deque a -> Bool Source # maximum :: Ord a => Deque a -> a Source # minimum :: Ord a => Deque a -> a Source # sum :: Num a => Deque a -> a Source # product :: Num a => Deque a -> a Source #
Traversable Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods traverse :: Applicative f => (a -> f b) -> Deque a -> f (Deque b) Source # sequenceA :: Applicative f => Deque (f a) -> f (Deque a) Source # mapM :: Monad m => (a -> m b) -> Deque a -> m (Deque b) Source # sequence :: Monad m => Deque (m a) -> m (Deque a) Source #
Alternative Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods empty :: Deque a Source # (<\|>) :: Deque a -> Deque a -> Deque a Source # some :: Deque a -> Deque [a] Source # many :: Deque a -> Deque [a] Source #
Applicative Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods pure :: a -> Deque a Source # (<>) :: Deque (a -> b) -> Deque a -> Deque b Source # liftA2 :: (a -> b -> c) -> Deque a -> Deque b -> Deque c Source # (>) :: Deque a -> Deque b -> Deque b Source # (<*) :: Deque a -> Deque b -> Deque a Source #
Functor Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods fmap :: (a -> b) -> Deque a -> Deque b Source # (<$) :: a -> Deque b -> Deque a Source #
Monad Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods (>>=) :: Deque a -> (a -> Deque b) -> Deque b Source # (>>) :: Deque a -> Deque b -> Deque b Source # return :: a -> Deque a Source #
MonadPlus Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods mzero :: Deque a Source # mplus :: Deque a -> Deque a -> Deque a Source #
Alt Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods (<!>) :: Deque a -> Deque a -> Deque a Source # some :: Applicative Deque => Deque a -> Deque [a] Source # many :: Applicative Deque => Deque a -> Deque [a] Source #
Apply Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods (<.>) :: Deque (a -> b) -> Deque a -> Deque b Source # (.>) :: Deque a -> Deque b -> Deque b Source # (<.) :: Deque a -> Deque b -> Deque a Source # liftF2 :: (a -> b -> c) -> Deque a -> Deque b -> Deque c Source #
Bind Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods (>>-) :: Deque a -> (a -> Deque b) -> Deque b Source # join :: Deque (Deque a) -> Deque a Source #
Plus Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods zero :: Deque a Source #
FoldableWithIndex Int Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods ifoldMap :: Monoid m => (Int -> a -> m) -> Deque a -> m Source # ifoldMap' :: Monoid m => (Int -> a -> m) -> Deque a -> m 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 Source #
Instance details Defined in Control.Lens.Internal.Deque Methods imap :: (Int -> a -> b) -> Deque a -> Deque b Source #
TraversableWithIndex Int Deque Source #
Instance details Defined in Control.Lens.Internal.Deque Methods itraverse :: Applicative f => (Int -> a -> f b) -> Deque a -> f (Deque b) Source #
Monoid (Deque a) Source #
Instance details Defined in Control.Lens.Internal.Deque Methods mempty :: Deque a Source # mappend :: Deque a -> Deque a -> Deque a Source # mconcat :: [Deque a] -> Deque a Source #
Semigroup (Deque a) Source #
Instance details Defined in Control.Lens.Internal.Deque Methods (<>) :: Deque a -> Deque a -> Deque a Source # sconcat :: NonEmpty (Deque a) -> Deque a Source # stimes :: Integral b => b -> Deque a -> Deque a Source #
Show a => Show (Deque a) Source #
Instance details Defined in Control.Lens.Internal.Deque Methods showsPrec :: Int -> Deque a -> ShowS Source # show :: Deque a -> String Source # showList :: [Deque a] -> ShowS Source #
Eq a => Eq (Deque a) Source #
Instance details Defined in Control.Lens.Internal.Deque Methods (==) :: Deque a -> Deque a -> Bool Source # (/=) :: Deque a -> Deque a -> Bool Source #
Ord a => Ord (Deque a) Source #
Instance details Defined in Control.Lens.Internal.Deque Methods compare :: Deque a -> Deque a -> Ordering Source # (<) :: Deque a -> Deque a -> Bool Source # (<=) :: Deque a -> Deque a -> Bool Source # (>) :: Deque a -> Deque a -> Bool Source # (>=) :: Deque a -> Deque a -> Bool Source # max :: Deque a -> Deque a -> Deque a Source # min :: Deque a -> Deque a -> Deque a Source #
Reversing (Deque a) Source #
Instance details Defined in Control.Lens.Internal.Deque Methods reversing :: Deque a -> Deque a Source #
Cons (Deque a) (Deque b) a b Source #
Instance details Defined in Control.Lens.Internal.Deque Methods _Cons :: Prism (Deque a) (Deque b) (a, Deque a) (b, Deque b) Source #
Snoc (Deque a) (Deque b) a b Source #
Instance details Defined in Control.Lens.Internal.Deque Methods _Snoc :: Prism (Deque a) (Deque b) (Deque a, a) (Deque b, 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.

>>> Control.Lens.Internal.Deque.null empty
True

>>> Control.Lens.Internal.Deque.null (singleton 1)
False

singleton :: a -> Deque a Source #

O(1). Generate a singleton Deque

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