deque-0.4.4.1: Double-ended queues
Safe HaskellSafe-Inferred
LanguageHaskell2010

Deque.Strict

Description

Definitions of strict Deque.

The typical toList and fromList conversions are provided by means of the Foldable and IsList instances.

Synopsis

Documentation

data Deque a Source #

Strict double-ended queue (aka Dequeue or Deque) based on head-tail linked list.

Instances

Instances details
MonadFail Deque Source # 
Instance details

Defined in Deque.Strict.Defs

Methods

fail :: String -> Deque a #

Foldable Deque Source # 
Instance details

Defined in Deque.Strict.Defs

Methods

fold :: Monoid m => Deque m -> m #

foldMap :: Monoid m => (a -> m) -> Deque a -> 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 Deque.Strict.Defs

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

Defined in Deque.Strict.Defs

Methods

empty :: Deque a #

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

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

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

Applicative Deque Source # 
Instance details

Defined in Deque.Strict.Defs

Methods

pure :: a -> Deque a #

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

liftA2 :: (a -> b -> c) -> Deque a -> Deque b -> Deque c #

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

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

Functor Deque Source # 
Instance details

Defined in Deque.Strict.Defs

Methods

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

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

Monad Deque Source # 
Instance details

Defined in Deque.Strict.Defs

Methods

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

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

return :: a -> Deque a #

MonadPlus Deque Source # 
Instance details

Defined in Deque.Strict.Defs

Methods

mzero :: Deque a #

mplus :: Deque a -> Deque a -> Deque a #

NFData1 Deque Source # 
Instance details

Defined in Deque.Strict.Defs

Methods

liftRnf :: (a -> ()) -> Deque a -> () #

Generic1 Deque Source # 
Instance details

Defined in Deque.Strict.Defs

Associated Types

type Rep1 Deque :: k -> Type #

Methods

from1 :: forall (a :: k). Deque a -> Rep1 Deque a #

to1 :: forall (a :: k). Rep1 Deque a -> Deque a #

Monoid (Deque a) Source # 
Instance details

Defined in Deque.Strict.Defs

Methods

mempty :: Deque a #

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

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

Semigroup (Deque a) Source # 
Instance details

Defined in Deque.Strict.Defs

Methods

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

sconcat :: NonEmpty (Deque a) -> Deque a #

stimes :: Integral b => b -> Deque a -> Deque a #

IsList (Deque a) Source # 
Instance details

Defined in Deque.Strict.Defs

Associated Types

type Item (Deque a) #

Methods

fromList :: [Item (Deque a)] -> Deque a #

fromListN :: Int -> [Item (Deque a)] -> Deque a #

toList :: Deque a -> [Item (Deque a)] #

Generic (Deque a) Source # 
Instance details

Defined in Deque.Strict.Defs

Associated Types

type Rep (Deque a) :: Type -> Type #

Methods

from :: Deque a -> Rep (Deque a) x #

to :: Rep (Deque a) x -> Deque a #

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

Defined in Deque.Strict.Defs

Methods

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

show :: Deque a -> String #

showList :: [Deque a] -> ShowS #

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

Defined in Deque.Strict.Defs

Methods

rnf :: Deque a -> () #

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

Defined in Deque.Strict.Defs

Methods

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

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

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

Defined in Deque.Strict.Defs

Methods

hashWithSalt :: Int -> Deque a -> Int #

hash :: Deque a -> Int #

type Rep1 Deque Source # 
Instance details

Defined in Deque.Strict.Defs

type Rep1 Deque = D1 ('MetaData "Deque" "Deque.Strict.Defs" "deque-0.4.4.1-AXJKR4g173k8gPaxixerqY" 'False) (C1 ('MetaCons "Deque" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec1 List) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec1 List)))
type Item (Deque a) Source # 
Instance details

Defined in Deque.Strict.Defs

type Item (Deque a) = a
type Rep (Deque a) Source # 
Instance details

Defined in Deque.Strict.Defs

type Rep (Deque a) = D1 ('MetaData "Deque" "Deque.Strict.Defs" "deque-0.4.4.1-AXJKR4g173k8gPaxixerqY" 'False) (C1 ('MetaCons "Deque" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (List a)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (List a))))

fromLazy :: Deque a -> Deque a Source #

Convert lazy deque to strict deque.

toLazy :: Deque a -> Deque a Source #

Convert strict deque to lazy deque.

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

\(\mathcal{O}(n)\). Construct from cons and snoc lists.

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

\(\mathcal{O}(1)\). Add element in the beginning.

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

\(\mathcal{O}(1)\). Add element in the ending.

reverse :: Deque a -> Deque a Source #

\(\mathcal{O}(1)\). Reverse the deque.

shiftLeft :: Deque a -> Deque a Source #

\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Move the first element to the end.

λ toList . shiftLeft $ fromList [1,2,3]
[2,3,1]

shiftRight :: Deque a -> Deque a Source #

\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Move the last element to the beginning.

λ toList . shiftRight $ fromList [1,2,3]
[3,1,2]

filter :: (a -> Bool) -> Deque a -> Deque a Source #

\(\mathcal{O}(n)\). Leave only the elements satisfying the predicate.

take :: Int -> Deque a -> Deque a Source #

\(\mathcal{O}(n)\). Leave only the specified amount of first elements.

drop :: Int -> Deque a -> Deque a Source #

\(\mathcal{O}(n)\). Drop the specified amount of first elements.

takeWhile :: (a -> Bool) -> Deque a -> Deque a Source #

\(\mathcal{O}(n)\). Leave only the first elements satisfying the predicate.

dropWhile :: (a -> Bool) -> Deque a -> Deque a Source #

\(\mathcal{O}(n)\). Drop the first elements satisfying the predicate.

span :: (a -> Bool) -> Deque a -> (Deque a, Deque a) Source #

\(\mathcal{O}(n)\). Perform takeWhile and dropWhile in a single operation.

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

\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the first element and deque without it if it's not empty.

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

\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the last element and deque without it if it's not empty.

null :: Deque a -> Bool Source #

\(\mathcal{O}(1)\). Check whether deque is empty.

head :: Deque a -> Maybe a Source #

\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the first element if deque is not empty.

last :: Deque a -> Maybe a Source #

\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the last element if deque is not empty.

tail :: Deque a -> Deque a Source #

\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Keep all elements but the first one.

In case of empty deque returns an empty deque.

init :: Deque a -> Deque a Source #

\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Keep all elements but the last one.

In case of empty deque returns an empty deque.