deque-0.4.4: Double-ended queues
Safe HaskellNone
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
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 #

Functor Deque Source # 
Instance details

Defined in Deque.Strict.Defs

Methods

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

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

MonadFail Deque Source # 
Instance details

Defined in Deque.Strict.Defs

Methods

fail :: String -> 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 #

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] #

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 -> () #

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)] #

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

Defined in Deque.Strict.Defs

Methods

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

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

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 #

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 #

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 #

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 #

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

Defined in Deque.Strict.Defs

Methods

rnf :: Deque a -> () #

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

Defined in Deque.Strict.Defs

Methods

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

hash :: Deque a -> Int #

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 #

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-9pLppH62QekKSsYLvhhJwi" '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))))
type Item (Deque a) Source # 
Instance details

Defined in Deque.Strict.Defs

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

Defined in Deque.Strict.Defs

type Rep1 Deque = D1 ('MetaData "Deque" "Deque.Strict.Defs" "deque-0.4.4-9pLppH62QekKSsYLvhhJwi" '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)))

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.