Deque.Strict

Definitions of strict Deque.

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

Documentation

data Deque a

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

Instances

Monad Deque

Defined in Deque.Strict

Methods

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

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

return :: a -> Deque a

fail :: String -> Deque a

Functor Deque

Defined in Deque.Strict

Methods

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

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

MonadFail Deque

Defined in Deque.Strict

Methods

fail :: String -> Deque a

Applicative Deque

Defined in Deque.Strict

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

Defined in Deque.Strict

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

Defined in Deque.Strict

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

Defined in Deque.Strict

Methods

empty :: Deque a

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

some :: Deque a -> Deque [a]

many :: Deque a -> Deque [a]

MonadPlus Deque

Defined in Deque.Strict

Methods

mzero :: Deque a

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

IsList (Deque a)

Defined in Deque.Strict

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)

Defined in Deque.Strict

Methods

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

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

Show a => Show (Deque a)

Defined in Deque.Strict

Methods

showsPrec :: Int -> Deque a -> ShowS

show :: Deque a -> String

showList :: [Deque a] -> ShowS

Semigroup (Deque a)

Defined in Deque.Strict

Methods

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

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

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

Monoid (Deque a)

Defined in Deque.Strict

Methods

mempty :: Deque a

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

mconcat :: [Deque a] -> Deque a

type Item (Deque a)

Defined in Deque.Strict

type Item (Deque a) = a

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

O(1). Construct from cons and snoc lists.

cons :: a -> Deque a -> Deque a

O(1). Add element in the beginning.

snoc :: a -> Deque a -> Deque a

O(1). Add element in the ending.

reverse :: Deque a -> Deque a

O(1). Revert the deque.

shiftLeft :: Deque a -> Deque a

O(1), occasionally O(n). Move the first element to the end.

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

shiftRight :: Deque a -> Deque a

O(1), occasionally 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

O(n). Leave only the elements satisfying the predicate.

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

O(n). Leave only the first elements satisfying the predicate.

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

O(n). Drop the first elements satisfying the predicate.

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

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

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

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

null :: Deque a -> Bool

O(1). Check whether deque is empty.

head :: Deque a -> Maybe a

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

last :: Deque a -> Maybe a

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

tail :: Deque a -> Deque a

O(1), occasionally O(n). Keep all elements but the first one.

In case of empty deque returns an empty deque.

init :: Deque a -> Deque a

O(1), occasionally O(n). Keep all elements but the last one.

In case of empty deque returns an empty deque.