-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Double-ended queues -- -- Strict and lazy implementations of Double-Ended Queue (aka Dequeue or -- Deque) based on head-tail linked list. @package deque @version 0.4 -- | Definitions of strict Deque. -- -- The typical toList and fromList conversions are provided -- by means of the Foldable and IsList instances. module Deque.Strict -- | Strict double-ended queue (aka Dequeue or Deque) based on head-tail -- linked list. data Deque a -- | Convert lazy deque to strict deque. fromLazy :: Deque a -> Deque a -- | Convert strict deque to lazy deque. toLazy :: Deque a -> Deque a -- | O(n). Construct from cons and snoc lists. fromConsAndSnocLists :: [a] -> [a] -> Deque a -- | O(1). Add element in the beginning. cons :: a -> Deque a -> Deque a -- | O(1). Add element in the ending. snoc :: a -> Deque a -> Deque a -- | O(1). Reverse the deque. reverse :: 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]
--
shiftLeft :: 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]
--
shiftRight :: Deque a -> Deque a -- | O(n). Leave only the elements satisfying the predicate. filter :: (a -> Bool) -> Deque a -> Deque a -- | O(n). Leave only the specified amount of first elements. take :: Int -> Deque a -> Deque a -- | O(n). Drop the specified amount of first elements. drop :: Int -> Deque a -> Deque a -- | O(n). Leave only the first elements satisfying the predicate. takeWhile :: (a -> Bool) -> Deque a -> Deque a -- | O(n). Drop the first elements satisfying the predicate. dropWhile :: (a -> Bool) -> Deque a -> Deque a -- | O(1), occasionally O(n). Get the first element and deque -- without it if it's not empty. uncons :: Deque a -> Maybe (a, Deque a) -- | O(1), occasionally O(n). Get the last element and deque -- without it if it's not empty. unsnoc :: Deque a -> Maybe (a, Deque a) -- | O(1). Check whether deque is empty. null :: Deque a -> Bool -- | O(1), occasionally O(n). Get the first element if deque -- is not empty. head :: Deque a -> Maybe a -- | O(1), occasionally O(n). Get the last element if deque -- is not empty. last :: Deque a -> Maybe a -- | O(1), occasionally O(n). Keep all elements but the first -- one. -- -- In case of empty deque returns an empty deque. tail :: 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. init :: Deque a -> Deque a -- | Definitions of lazy Deque. -- -- The typical toList and fromList conversions are provided -- by means of the Foldable and IsList instances. module Deque.Lazy -- | Lazy double-ended queue (aka Dequeue or Deque) based on head-tail -- linked list. data Deque a -- | Convert strict deque to lazy deque. fromStrict :: Deque a -> Deque a -- | Convert lazy deque to strict deque. toStrict :: Deque a -> Deque a -- | O(1). Construct from cons and snoc lists. fromConsAndSnocLists :: [a] -> [a] -> Deque a -- | O(1). Add element in the beginning. cons :: a -> Deque a -> Deque a -- | O(1). Add element in the ending. snoc :: a -> Deque a -> Deque a -- | O(1). Reverse the deque. reverse :: 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]
--
shiftLeft :: 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]
--
shiftRight :: Deque a -> Deque a -- | O(n). Leave only the elements satisfying the predicate. filter :: (a -> Bool) -> Deque a -> Deque a -- | O(n). Leave only the specified amount of first elements. take :: Int -> Deque a -> Deque a -- | O(n). Drop the specified amount of first elements. drop :: Int -> Deque a -> Deque a -- | O(n). Leave only the first elements satisfying the predicate. takeWhile :: (a -> Bool) -> Deque a -> Deque a -- | O(n). Drop the first elements satisfying the predicate. dropWhile :: (a -> Bool) -> Deque a -> Deque a -- | O(1), occasionally O(n). Get the first element and deque -- without it if it's not empty. uncons :: Deque a -> Maybe (a, Deque a) -- | O(1), occasionally O(n). Get the last element and deque -- without it if it's not empty. unsnoc :: Deque a -> Maybe (a, Deque a) -- | O(1). Check whether deque is empty. null :: Deque a -> Bool -- | O(1), occasionally O(n). Get the first element if deque -- is not empty. head :: Deque a -> Maybe a -- | O(1), occasionally O(n). Get the last element if deque -- is not empty. last :: Deque a -> Maybe a -- | O(1), occasionally O(n). Keep all elements but the first -- one. -- -- In case of empty deque returns an empty deque. tail :: 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. init :: Deque a -> Deque a -- | Lazy Deque API lifted to a State monad, "mtl"-style. module Deque.Lazy.State -- | O(n). Modify each element of the queue. map :: MonadState (Deque a) m => (a -> a) -> m () -- | O(n). Add elements to the begginning. prepend :: MonadState (Deque a) m => Deque a -> m () -- | O(n). Add elements to the ending. append :: MonadState (Deque a) m => Deque a -> m () -- | O(1). Add element in the beginning. cons :: MonadState (Deque a) m => a -> m () -- | O(1). Add element in the ending. snoc :: MonadState (Deque a) m => a -> m () -- | O(1). Reverse the deque. reverse :: MonadState (Deque a) m => m () -- | O(1), occasionally O(n). Move the first element to the -- end. shiftLeft :: MonadState (Deque a) m => m () -- | O(1), occasionally O(n). Move the last element to the -- beginning. shiftRight :: MonadState (Deque a) m => m () -- | O(n). Leave only the elements satisfying the predicate. filter :: MonadState (Deque a) m => (a -> Bool) -> m () -- | O(n). Leave only the specified amount of first elements. take :: MonadState (Deque a) m => Int -> m () -- | O(n). Drop the specified amount of first elements. drop :: MonadState (Deque a) m => Int -> m () -- | O(n). Leave only the first elements satisfying the predicate. takeWhile :: MonadState (Deque a) m => (a -> Bool) -> m () -- | O(n). Drop the first elements satisfying the predicate. dropWhile :: MonadState (Deque a) m => (a -> Bool) -> m () -- | O(1), occasionally O(n). Get the first element and deque -- without it if it's not empty. uncons :: MonadState (Deque a) m => m (Maybe a) -- | O(1), occasionally O(n). Get the last element and deque -- without it if it's not empty. unsnoc :: MonadState (Deque a) m => m (Maybe a) -- | O(1). Check whether deque is empty. null :: MonadState (Deque a) m => m Bool -- | O(1). Check whether deque is empty. length :: MonadState (Deque a) m => m Int -- | O(1), occasionally O(n). Get the first element if deque -- is not empty. head :: MonadState (Deque a) m => m (Maybe a) -- | O(1), occasionally O(n). Get the last element if deque -- is not empty. last :: MonadState (Deque a) m => m (Maybe a) -- | O(1), occasionally O(n). Keep all elements but the first -- one. tail :: MonadState (Deque a) m => m () -- | O(1), occasionally O(n). Keep all elements but the last -- one. init :: MonadState (Deque a) m => m () -- | Lazy Deque API lifted to a Reader monad, "mtl"-style. module Deque.Lazy.Reader -- | O(n). Modify each element of the queue. map :: MonadReader (Deque a) m => (a -> b) -> m (Deque b) -- | O(n). Add elements to the begginning. prepend :: MonadReader (Deque a) m => Deque a -> m (Deque a) -- | O(n). Add elements to the ending. append :: MonadReader (Deque a) m => Deque a -> m (Deque a) -- | O(1). Add element in the beginning. cons :: MonadReader (Deque a) m => a -> m (Deque a) -- | O(1). Add element in the ending. snoc :: MonadReader (Deque a) m => a -> m (Deque a) -- | O(1). Reverse the deque. reverse :: MonadReader (Deque a) m => m (Deque a) -- | O(1), occasionally O(n). Move the first element to the -- end. shiftLeft :: MonadReader (Deque a) m => m (Deque a) -- | O(1), occasionally O(n). Move the last element to the -- beginning. shiftRight :: MonadReader (Deque a) m => m (Deque a) -- | O(n). Leave only the elements satisfying the predicate. filter :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) -- | O(n). Leave only the specified amount of first elements. take :: MonadReader (Deque a) m => Int -> m (Deque a) -- | O(n). Drop the specified amount of first elements. drop :: MonadReader (Deque a) m => Int -> m (Deque a) -- | O(n). Leave only the first elements satisfying the predicate. takeWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) -- | O(n). Drop the first elements satisfying the predicate. dropWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) -- | O(1), occasionally O(n). Get the first element and deque -- without it if it's not empty. uncons :: MonadReader (Deque a) m => m (Maybe a, Deque a) -- | O(1), occasionally O(n). Get the last element and deque -- without it if it's not empty. unsnoc :: MonadReader (Deque a) m => m (Maybe a, Deque a) -- | O(1). Check whether deque is empty. null :: MonadReader (Deque a) m => m Bool -- | O(1). Check whether deque is empty. length :: MonadReader (Deque a) m => m Int -- | O(1), occasionally O(n). Get the first element if deque -- is not empty. head :: MonadReader (Deque a) m => m (Maybe a) -- | O(1), occasionally O(n). Get the last element if deque -- is not empty. last :: MonadReader (Deque a) m => m (Maybe a) -- | O(1), occasionally O(n). Keep all elements but the first -- one. tail :: MonadReader (Deque a) m => m (Deque a) -- | O(1), occasionally O(n). Keep all elements but the last -- one. init :: MonadReader (Deque a) m => m (Deque a) -- | Strict Deque API lifted to a Reader monad, "mtl"-style. module Deque.Strict.Reader -- | O(n). Modify each element of the queue. map :: MonadReader (Deque a) m => (a -> b) -> m (Deque b) -- | O(n). Add elements to the begginning. prepend :: MonadReader (Deque a) m => Deque a -> m (Deque a) -- | O(n). Add elements to the ending. append :: MonadReader (Deque a) m => Deque a -> m (Deque a) -- | O(1). Add element in the beginning. cons :: MonadReader (Deque a) m => a -> m (Deque a) -- | O(1). Add element in the ending. snoc :: MonadReader (Deque a) m => a -> m (Deque a) -- | O(1). Reverse the deque. reverse :: MonadReader (Deque a) m => m (Deque a) -- | O(1), occasionally O(n). Move the first element to the -- end. shiftLeft :: MonadReader (Deque a) m => m (Deque a) -- | O(1), occasionally O(n). Move the last element to the -- beginning. shiftRight :: MonadReader (Deque a) m => m (Deque a) -- | O(n). Leave only the elements satisfying the predicate. filter :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) -- | O(n). Leave only the specified amount of first elements. take :: MonadReader (Deque a) m => Int -> m (Deque a) -- | O(n). Drop the specified amount of first elements. drop :: MonadReader (Deque a) m => Int -> m (Deque a) -- | O(n). Leave only the first elements satisfying the predicate. takeWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) -- | O(n). Drop the first elements satisfying the predicate. dropWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) -- | O(1), occasionally O(n). Get the first element and deque -- without it if it's not empty. uncons :: MonadReader (Deque a) m => m (Maybe a, Deque a) -- | O(1), occasionally O(n). Get the last element and deque -- without it if it's not empty. unsnoc :: MonadReader (Deque a) m => m (Maybe a, Deque a) -- | O(1). Check whether deque is empty. null :: MonadReader (Deque a) m => m Bool -- | O(1). Check whether deque is empty. length :: MonadReader (Deque a) m => m Int -- | O(1), occasionally O(n). Get the first element if deque -- is not empty. head :: MonadReader (Deque a) m => m (Maybe a) -- | O(1), occasionally O(n). Get the last element if deque -- is not empty. last :: MonadReader (Deque a) m => m (Maybe a) -- | O(1), occasionally O(n). Keep all elements but the first -- one. tail :: MonadReader (Deque a) m => m (Deque a) -- | O(1), occasionally O(n). Keep all elements but the last -- one. init :: MonadReader (Deque a) m => m (Deque a) -- | Strict Deque API lifted to a State monad, "mtl"-style. module Deque.Strict.State -- | O(n). Modify each element of the queue. map :: MonadState (Deque a) m => (a -> a) -> m () -- | O(n). Add elements to the begginning. prepend :: MonadState (Deque a) m => Deque a -> m () -- | O(n). Add elements to the ending. append :: MonadState (Deque a) m => Deque a -> m () -- | O(1). Add element in the beginning. cons :: MonadState (Deque a) m => a -> m () -- | O(1). Add element in the ending. snoc :: MonadState (Deque a) m => a -> m () -- | O(1). Reverse the deque. reverse :: MonadState (Deque a) m => m () -- | O(1), occasionally O(n). Move the first element to the -- end. shiftLeft :: MonadState (Deque a) m => m () -- | O(1), occasionally O(n). Move the last element to the -- beginning. shiftRight :: MonadState (Deque a) m => m () -- | O(n). Leave only the elements satisfying the predicate. filter :: MonadState (Deque a) m => (a -> Bool) -> m () -- | O(n). Leave only the specified amount of first elements. take :: MonadState (Deque a) m => Int -> m () -- | O(n). Drop the specified amount of first elements. drop :: MonadState (Deque a) m => Int -> m () -- | O(n). Leave only the first elements satisfying the predicate. takeWhile :: MonadState (Deque a) m => (a -> Bool) -> m () -- | O(n). Drop the first elements satisfying the predicate. dropWhile :: MonadState (Deque a) m => (a -> Bool) -> m () -- | O(1), occasionally O(n). Get the first element and deque -- without it if it's not empty. uncons :: MonadState (Deque a) m => m (Maybe a) -- | O(1), occasionally O(n). Get the last element and deque -- without it if it's not empty. unsnoc :: MonadState (Deque a) m => m (Maybe a) -- | O(1). Check whether deque is empty. null :: MonadState (Deque a) m => m Bool -- | O(1). Check whether deque is empty. length :: MonadState (Deque a) m => m Int -- | O(1), occasionally O(n). Get the first element if deque -- is not empty. head :: MonadState (Deque a) m => m (Maybe a) -- | O(1), occasionally O(n). Get the last element if deque -- is not empty. last :: MonadState (Deque a) m => m (Maybe a) -- | O(1), occasionally O(n). Keep all elements but the first -- one. tail :: MonadState (Deque a) m => m () -- | O(1), occasionally O(n). Keep all elements but the last -- one. init :: MonadState (Deque a) m => m ()