deque-0.4.4: Double-ended queues

Safe Haskell | Safe-Inferred
Language | Haskell2010

Deque.Lazy

Description

Definitions of lazy Deque.

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

Synopsis

- data Deque a
- fromStrict :: Deque a -> Deque a
- toStrict :: Deque a -> Deque a
- fromConsAndSnocLists :: [a] -> [a] -> Deque a
- cons :: a -> Deque a -> Deque a
- snoc :: a -> Deque a -> Deque a
- reverse :: Deque a -> Deque a
- shiftLeft :: Deque a -> Deque a
- shiftRight :: Deque a -> Deque a
- filter :: (a -> Bool) -> Deque a -> Deque a
- take :: Int -> Deque a -> Deque a
- drop :: Int -> Deque a -> Deque a
- takeWhile :: (a -> Bool) -> Deque a -> Deque a
- dropWhile :: (a -> Bool) -> Deque a -> Deque a
- span :: (a -> Bool) -> Deque a -> (Deque a, Deque a)
- uncons :: Deque a -> Maybe (a, Deque a)
- unsnoc :: Deque a -> Maybe (a, Deque a)
- null :: Deque a -> Bool
- head :: Deque a -> Maybe a
- last :: Deque a -> Maybe a
- tail :: Deque a -> Deque a
- init :: Deque a -> Deque a

# Documentation

data Deque a Source #

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

#### Instances

Instances details

MonadFail Deque Source # |
Instance details Defined in Deque.Lazy.Defs Methods fail :: String -> Deque a Source #
Foldable Deque Source # |

Instance details

Defined in Deque.Lazy.Defs

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 Deque.Lazy.Defs 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 Deque.Lazy.Defs 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 Deque.Lazy.Defs 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 Deque.Lazy.Defs Methods fmap :: (a -> b) -> Deque a -> Deque b Source # (<$) :: a -> Deque b -> Deque a Source #
Monad Deque Source # |
Instance details Defined in Deque.Lazy.Defs 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 Deque.Lazy.Defs Methods mzero :: Deque a Source # mplus :: Deque a -> Deque a -> Deque a Source #
NFData1 Deque Source # |
Instance details Defined in Deque.Lazy.Defs Methods liftRnf :: (a -> ()) -> Deque a -> () Source #
Generic1 Deque Source # |
Instance details Defined in Deque.Lazy.Defs Associated Types type Rep1 Deque :: k -> Type Source # Methods from1 :: forall (a :: k). Deque a -> Rep1 Deque a Source # to1 :: forall (a :: k). Rep1 Deque a -> Deque a Source #
Monoid (Deque a) Source # |
Instance details Defined in Deque.Lazy.Defs 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 Deque.Lazy.Defs Methods (<>) :: Deque a -> Deque a -> Deque a Source # sconcat :: NonEmpty (Deque a) -> Deque a Source # stimes :: Integral b => b -> Deque a -> Deque a Source #
Generic (Deque a) Source # |
Instance details Defined in Deque.Lazy.Defs Associated Types type Rep (Deque a) :: Type -> Type Source # Methods from :: Deque a -> Rep (Deque a) x Source # to :: Rep (Deque a) x -> Deque a Source #
IsList (Deque a) Source # | \(\mathcal{O}(1)\).
Instance details Defined in Deque.Lazy.Defs Associated Types type Item (Deque a) Source # Methods fromList :: [Item (Deque a)] -> Deque a Source # fromListN :: Int -> [Item (Deque a)] -> Deque a Source # toList :: Deque a -> [Item (Deque a)] Source #
Show a => Show (Deque a) Source # |
Instance details Defined in Deque.Lazy.Defs Methods showsPrec :: Int -> Deque a -> ShowS Source # show :: Deque a -> String Source # showList :: [Deque a] -> ShowS Source #
NFData a => NFData (Deque a) Source # |
Instance details Defined in Deque.Lazy.Defs Methods rnf :: Deque a -> () Source #
Eq a => Eq (Deque a) Source # |
Instance details Defined in Deque.Lazy.Defs Methods (==) :: Deque a -> Deque a -> Bool Source # (/=) :: Deque a -> Deque a -> Bool Source #
Hashable a => Hashable (Deque a) Source # |
Instance details Defined in Deque.Lazy.Defs Methods hashWithSalt :: Int -> Deque a -> Int Source # hash :: Deque a -> Int Source #
type Rep1 Deque Source # |
Instance details Defined in Deque.Lazy.Defs type Rep1 Deque = D1 ('MetaData "Deque" "Deque.Lazy.Defs" "deque-0.4.4-9jnsW1lozQEHI49qbz87jm" 'False) (C1 ('MetaCons "Deque" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec1 []) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec1 [])))
type Rep (Deque a) Source # |

Instance details

Defined in Deque.Lazy.Defs

type Rep (Deque a) = D1 ('MetaData "Deque" "Deque.Lazy.Defs" "deque-0.4.4-9jnsW1lozQEHI49qbz87jm" 'False) (C1 ('MetaCons "Deque" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 [a]) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 [a])))

type Item (Deque a) Source # |
Instance details Defined in Deque.Lazy.Defs type Item (Deque a) = a

fromStrict :: Deque a -> Deque a Source #

Convert strict deque to lazy deque.

toStrict :: Deque a -> Deque a Source #

Convert lazy deque to strict deque.

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

\(\mathcal{O}(1)\). 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.