Deque

Documentation

data Deque a

Double-ended queue (aka Dequeue or Deque) based on the head-tail linked list. Can be cycled. See shiftLeft and shiftRight.

Constructors

Deque [a] [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)

Eq a => Eq (Deque a)

Methods

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

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

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

fromList :: [a] -> Deque a

O(1). toList is available from the Foldable instance.

shiftLeft :: Deque a -> Deque a

O(1), occasionally O(n).

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

shiftRight :: Deque a -> Deque a

O(1), occasionally O(n).

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

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

O(1). Prepend an element.

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

O(1). Append an element.

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

O(1), occasionally O(n).

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

O(1), occasionally O(n).

prepend :: Deque a -> Deque a -> Deque a

O(n).

reverse :: Deque a -> Deque a

O(1).

head :: Deque a -> Maybe a

O(1), occasionally O(n).

tail :: Deque a -> Deque a

O(1), occasionally O(n).

init :: Deque a -> Deque a

O(1), occasionally O(n).

last :: Deque a -> Maybe a

O(1), occasionally O(n).