deque 0.4.3 → 0.4.4

raw patch · 8 files changed

+146/−132 lines, 8 filesdep +deepseqdep ~strict-listPVP ok

version bump matches the API change (PVP)

Dependencies added: deepseq

Dependency ranges changed: strict-list

API changes (from Hackage documentation)

Files

• deque.cabal +3/−2
• library/Deque/Lazy/Defs.hs +24/−21
• library/Deque/Lazy/Reader.hs +22/−22
• library/Deque/Lazy/State.hs +22/−22
• library/Deque/Prelude.hs +4/−0
• library/Deque/Strict/Defs.hs +27/−21
• library/Deque/Strict/Reader.hs +22/−22
• library/Deque/Strict/State.hs +22/−22

@@ -1,5 +1,5 @@ name: deque-version: 0.4.3+version: 0.4.4 synopsis: Double-ended queues description:   Strict and lazy implementations of Double-Ended Queue (aka Dequeue or Deque)@@ -36,9 +36,10 @@     Deque.Prelude   build-depends:     base >=4.9 && <5,+    deepseq >=1.4.3 && <1.5,     hashable >=1.2 && <2,     mtl >=2.2 && <3,-    strict-list >=0.1.5 && <0.2+    strict-list >=0.1.6 && <0.2  test-suite test   type: exitcode-stdio-1.0

@@ -18,19 +18,19 @@ data Deque a = Deque ![a] ![a]  -- |--- /O(1)/.+-- \(\mathcal{O}(1)\). -- Construct from cons and snoc lists. fromConsAndSnocLists :: [a] -> [a] -> Deque a fromConsAndSnocLists consList snocList = Deque consList snocList  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Leave only the elements satisfying the predicate. filter :: (a -> Bool) -> Deque a -> Deque a filter predicate (Deque consList snocList) = Deque (List.filter predicate consList) (List.filter predicate snocList)  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Leave only the specified amount of first elements. take :: Int -> Deque a -> Deque a take amount (Deque consList snocList) = let@@ -49,7 +49,7 @@   in Deque newConsList []  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Drop the specified amount of first elements. drop :: Int -> Deque a -> Deque a drop amount (Deque consList snocList) = let@@ -66,7 +66,7 @@   in buildFromConsList amount consList  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Leave only the first elements satisfying the predicate. takeWhile :: (a -> Bool) -> Deque a -> Deque a takeWhile predicate (Deque consList snocList) = let@@ -79,7 +79,7 @@   in Deque newConsList []  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Drop the first elements satisfying the predicate. dropWhile :: (a -> Bool) -> Deque a -> Deque a dropWhile predicate (Deque consList snocList) = let@@ -89,7 +89,7 @@     _ -> Deque newConsList snocList  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Perform `takeWhile` and `dropWhile` in a single operation. span :: (a -> Bool) -> Deque a -> (Deque a, Deque a) span predicate (Deque consList snocList) = case List.span predicate consList of@@ -105,7 +105,7 @@       in (prefix, suffix)  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Move the first element to the end. -- -- @@@ -116,7 +116,7 @@ shiftLeft deque = maybe deque (uncurry snoc) (uncons deque)  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Move the last element to the beginning. -- -- @@@ -127,19 +127,19 @@ shiftRight deque = maybe deque (uncurry cons) (unsnoc deque)  -- |--- /O(1)/.+-- \(\mathcal{O}(1)\). -- Add element in the beginning. cons :: a -> Deque a -> Deque a cons a (Deque consList snocList) = Deque (a : consList) snocList  -- |--- /O(1)/.+-- \(\mathcal{O}(1)\). -- Add element in the ending. snoc :: a -> Deque a -> Deque a snoc a (Deque consList snocList) = Deque consList (a : snocList)  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the first element and deque without it if it's not empty. uncons :: Deque a -> Maybe (a, Deque a) uncons (Deque consList snocList) = case consList of@@ -149,7 +149,7 @@     _ -> Nothing  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the last element and deque without it if it's not empty. unsnoc :: Deque a -> Maybe (a, Deque a) unsnoc (Deque consList snocList) = case snocList of@@ -159,7 +159,7 @@     _ -> Nothing  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). prepend :: Deque a -> Deque a -> Deque a prepend (Deque consList1 snocList1) (Deque consList2 snocList2) = let   consList = consList1@@ -167,25 +167,25 @@   in Deque consList snocList  -- |--- /O(1)/.+-- \(\mathcal{O}(1)\). -- Reverse the deque. reverse :: Deque a -> Deque a reverse (Deque consList snocList) = Deque snocList consList  -- |--- /O(1)/. +-- \(\mathcal{O}(1)\).  -- Check whether deque is empty. null :: Deque a -> Bool null (Deque consList snocList) = List.null snocList && List.null consList  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the first element if deque is not empty. head :: Deque a -> Maybe a head = fmap fst . uncons  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Keep all elements but the first one. --  -- In case of empty deque returns an empty deque.@@ -193,7 +193,7 @@ tail = fromMaybe <$> id <*> fmap snd . uncons  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Keep all elements but the last one. --  -- In case of empty deque returns an empty deque.@@ -201,7 +201,7 @@ init = fromMaybe <$> id <*> fmap snd . unsnoc  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the last element if deque is not empty. last :: Deque a -> Maybe a last = fmap fst . unsnoc@@ -266,7 +266,7 @@   fail = const mempty  -- |--- /O(1)/.+-- \(\mathcal{O}(1)\). instance IsList (Deque a) where   type Item (Deque a) = a   fromList = flip Deque []@@ -276,3 +276,6 @@ deriving instance Generic1 Deque  instance Hashable a => Hashable (Deque a)++instance NFData a => NFData (Deque a)+instance NFData1 Deque

@@ -11,105 +11,105 @@   {-|-/O(n)/.+\(\mathcal{O}(n)\). Modify each element of the queue. -} map :: MonadReader (Deque a) m => (a -> b) -> m (Deque b) map f = reader (fmap f)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Add elements to the begginning. -} prepend :: MonadReader (Deque a) m => Deque a -> m (Deque a) prepend deque = reader (deque <>)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Add elements to the ending. -} append :: MonadReader (Deque a) m => Deque a -> m (Deque a) append deque = reader (<> deque)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Add element in the beginning. -} cons :: MonadReader (Deque a) m => a -> m (Deque a) cons a = reader (Deque.cons a)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Add element in the ending. -} snoc :: MonadReader (Deque a) m => a -> m (Deque a) snoc a = reader (Deque.snoc a)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Reverse the deque. -} reverse :: MonadReader (Deque a) m => m (Deque a) reverse = reader Deque.reverse  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Move the first element to the end. -} shiftLeft :: MonadReader (Deque a) m => m (Deque a) shiftLeft = reader Deque.shiftLeft  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Move the last element to the beginning. -} shiftRight :: MonadReader (Deque a) m => m (Deque a) shiftRight = reader Deque.shiftRight  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the elements satisfying the predicate. -} filter :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) filter predicate = reader (Deque.filter predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the specified amount of first elements. -} take :: MonadReader (Deque a) m => Int -> m (Deque a) take = reader . Deque.take  {-|-/O(n)/.+\(\mathcal{O}(n)\). Drop the specified amount of first elements. -} drop :: MonadReader (Deque a) m => Int -> m (Deque a) drop = reader . Deque.drop  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the first elements satisfying the predicate. -} takeWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) takeWhile predicate = reader (Deque.takeWhile predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Drop the first elements satisfying the predicate. -} dropWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) dropWhile predicate = reader (Deque.dropWhile predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Same as @(,) '<$>' `takeWhile` predicate '<*>' `dropWhile` predicate@. -} span :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a, Deque a) span predicate = reader (Deque.span predicate)  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{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)@@ -118,7 +118,7 @@   Just (a, newDeque) -> (Just a, newDeque))  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{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)@@ -127,42 +127,42 @@   Just (a, newDeque) -> (Just a, newDeque))  {-|-/O(1)/. +\(\mathcal{O}(1)\).  Check whether deque is empty. -} null :: MonadReader (Deque a) m => m Bool null = reader Deque.null  {-|-/O(1)/. +\(\mathcal{O}(1)\).  Check whether deque is empty. -} length :: MonadReader (Deque a) m => m Int length = reader Prelude.length  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the first element if deque is not empty. -} head :: MonadReader (Deque a) m => m (Maybe a) head = reader Deque.head  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the last element if deque is not empty. -} last :: MonadReader (Deque a) m => m (Maybe a) last = reader Deque.last  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Keep all elements but the first one. -} tail :: MonadReader (Deque a) m => m (Deque a) tail = reader Deque.tail  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Keep all elements but the last one. -} init :: MonadReader (Deque a) m => m (Deque a)

@@ -11,105 +11,105 @@   {-|-/O(n)/.+\(\mathcal{O}(n)\). Modify each element of the queue. -} map :: MonadState (Deque a) m => (a -> a) -> m () map f = modify (fmap f)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Add elements to the begginning. -} prepend :: MonadState (Deque a) m => Deque a -> m () prepend deque = modify (deque <>)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Add elements to the ending. -} append :: MonadState (Deque a) m => Deque a -> m () append deque = modify (<> deque)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Add element in the beginning. -} cons :: MonadState (Deque a) m => a -> m () cons a = modify (Deque.cons a)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Add element in the ending. -} snoc :: MonadState (Deque a) m => a -> m () snoc a = modify (Deque.snoc a)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Reverse the deque. -} reverse :: MonadState (Deque a) m => m () reverse = modify Deque.reverse  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Move the first element to the end. -} shiftLeft :: MonadState (Deque a) m => m () shiftLeft = modify Deque.shiftLeft  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Move the last element to the beginning. -} shiftRight :: MonadState (Deque a) m => m () shiftRight = modify Deque.shiftRight  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the elements satisfying the predicate. -} filter :: MonadState (Deque a) m => (a -> Bool) -> m () filter predicate = modify (Deque.filter predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the specified amount of first elements. -} take :: MonadState (Deque a) m => Int -> m () take = modify . Deque.take  {-|-/O(n)/.+\(\mathcal{O}(n)\). Drop the specified amount of first elements. -} drop :: MonadState (Deque a) m => Int -> m () drop = modify . Deque.drop  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the first elements satisfying the predicate. -} takeWhile :: MonadState (Deque a) m => (a -> Bool) -> m () takeWhile predicate = modify (Deque.takeWhile predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Drop the first elements satisfying the predicate. -} dropWhile :: MonadState (Deque a) m => (a -> Bool) -> m () dropWhile predicate = modify (Deque.dropWhile predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Return the first elements satisfying the predicate, removing them from the state. -} span :: MonadState (Deque a) m => (a -> Bool) -> m (Deque a) span predicate = state (Deque.span predicate)  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the first element if deque is not empty, removing the element. -}@@ -119,7 +119,7 @@   Just (a, newDeque) -> (Just a, newDeque))  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the last element if deque is not empty, removing the element. -}@@ -129,42 +129,42 @@   Just (a, newDeque) -> (Just a, newDeque))  {-|-/O(1)/. +\(\mathcal{O}(1)\).  Check whether deque is empty. -} null :: MonadState (Deque a) m => m Bool null = gets Deque.null  {-|-/O(1)/. +\(\mathcal{O}(1)\).  Check whether deque is empty. -} length :: MonadState (Deque a) m => m Int length = gets Prelude.length  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the first element if deque is not empty. -} head :: MonadState (Deque a) m => m (Maybe a) head = gets Deque.head  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the last element if deque is not empty. -} last :: MonadState (Deque a) m => m (Maybe a) last = gets Deque.last  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Keep all elements but the first one. -} tail :: MonadState (Deque a) m => m () tail = modify Deque.tail  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Keep all elements but the last one. -} init :: MonadState (Deque a) m => m ()

@@ -83,3 +83,7 @@ -- hashable ------------------------- import Data.Hashable as Exports (Hashable)++-- deepseq+-------------------------+import Control.DeepSeq as Exports

@@ -18,31 +18,31 @@ data Deque a = Deque !(StrictList.List a) !(StrictList.List a)  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Construct from cons and snoc lists. fromConsAndSnocLists :: [a] -> [a] -> Deque a fromConsAndSnocLists consList snocList = Deque (fromList consList) (fromList snocList)  -- |--- /O(1)/.+-- \(\mathcal{O}(1)\). -- Add element in the beginning. cons :: a -> Deque a -> Deque a cons a (Deque consList snocList) = Deque (StrictList.Cons a consList) snocList  -- |--- /O(1)/.+-- \(\mathcal{O}(1)\). -- Add element in the ending. snoc :: a -> Deque a -> Deque a snoc a (Deque consList snocList) = Deque consList (StrictList.Cons a snocList)  -- |--- /O(1)/.+-- \(\mathcal{O}(1)\). -- Reverse the deque. reverse :: Deque a -> Deque a reverse (Deque consList snocList) = Deque snocList consList  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Move the first element to the end. -- -- @@@ -53,7 +53,7 @@ shiftLeft deque = maybe deque (uncurry snoc) (uncons deque)  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Move the last element to the beginning. -- -- @@@ -63,8 +63,11 @@ shiftRight :: Deque a -> Deque a shiftRight deque = maybe deque (uncurry cons) (unsnoc deque) +balanceLeft :: Deque a -> Deque a+balanceLeft = error "TODO"+ -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Leave only the elements satisfying the predicate. filter :: (a -> Bool) -> Deque a -> Deque a filter predicate (Deque consList snocList) = let@@ -74,7 +77,7 @@   in Deque newConsList StrictList.Nil  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Leave only the specified amount of first elements. take :: Int -> Deque a -> Deque a take amount (Deque consList snocList) = let@@ -93,7 +96,7 @@   in Deque StrictList.Nil newSnocList  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Drop the specified amount of first elements. drop :: Int -> Deque a -> Deque a drop amount (Deque consList snocList) = let@@ -110,7 +113,7 @@   in buildFromConsList amount consList  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Leave only the first elements satisfying the predicate. takeWhile :: (a -> Bool) -> Deque a -> Deque a takeWhile predicate (Deque consList snocList) = let@@ -123,7 +126,7 @@   in Deque newConsList StrictList.Nil  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Drop the first elements satisfying the predicate. dropWhile :: (a -> Bool) -> Deque a -> Deque a dropWhile predicate (Deque consList snocList) = let@@ -133,7 +136,7 @@     _ -> Deque newConsList snocList  -- |--- /O(n)/.+-- \(\mathcal{O}(n)\). -- Perform `takeWhile` and `dropWhile` in a single operation. span :: (a -> Bool) -> Deque a -> (Deque a, Deque a) span predicate (Deque consList snocList) = case StrictList.spanReversed predicate consList of@@ -149,7 +152,7 @@       in (prefix, suffix)  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the first element and deque without it if it's not empty. uncons :: Deque a -> Maybe (a, Deque a) uncons (Deque consList snocList) = case consList of@@ -159,7 +162,7 @@     _ -> Nothing  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the last element and deque without it if it's not empty. unsnoc :: Deque a -> Maybe (a, Deque a) unsnoc (Deque consList snocList) = case snocList of@@ -169,7 +172,7 @@     _ -> Nothing  -- |--- /O(1)/. +-- \(\mathcal{O}(1)\).  -- Check whether deque is empty. null :: Deque a -> Bool null = \ case@@ -177,7 +180,7 @@   _ -> False  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the first element if deque is not empty. head :: Deque a -> Maybe a head (Deque consList snocList) = case consList of@@ -185,7 +188,7 @@   _ -> StrictList.last snocList  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the last element if deque is not empty. last :: Deque a -> Maybe a last (Deque consList snocList) = case snocList of@@ -193,17 +196,17 @@   _ -> StrictList.last consList  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Keep all elements but the first one. --  -- In case of empty deque returns an empty deque. tail :: Deque a -> Deque a tail (Deque consList snocList) = case consList of-  StrictList.Nil -> Deque (StrictList.initReversed snocList) StrictList.Nil-  _ -> Deque (StrictList.tail consList) snocList+  StrictList.Cons _ consListTail -> Deque consListTail snocList+  _ -> Deque (StrictList.initReversed snocList) StrictList.Nil  -- |--- /O(1)/, occasionally /O(n)/.+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Keep all elements but the last one. --  -- In case of empty deque returns an empty deque.@@ -281,3 +284,6 @@ deriving instance Generic1 Deque  instance Hashable a => Hashable (Deque a)++instance NFData a => NFData (Deque a)+instance NFData1 Deque

@@ -11,105 +11,105 @@   {-|-/O(n)/.+\(\mathcal{O}(n)\). Modify each element of the queue. -} map :: MonadReader (Deque a) m => (a -> b) -> m (Deque b) map f = reader (fmap f)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Add elements to the begginning. -} prepend :: MonadReader (Deque a) m => Deque a -> m (Deque a) prepend deque = reader (deque <>)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Add elements to the ending. -} append :: MonadReader (Deque a) m => Deque a -> m (Deque a) append deque = reader (<> deque)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Add element in the beginning. -} cons :: MonadReader (Deque a) m => a -> m (Deque a) cons a = reader (Deque.cons a)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Add element in the ending. -} snoc :: MonadReader (Deque a) m => a -> m (Deque a) snoc a = reader (Deque.snoc a)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Reverse the deque. -} reverse :: MonadReader (Deque a) m => m (Deque a) reverse = reader Deque.reverse  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Move the first element to the end. -} shiftLeft :: MonadReader (Deque a) m => m (Deque a) shiftLeft = reader Deque.shiftLeft  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Move the last element to the beginning. -} shiftRight :: MonadReader (Deque a) m => m (Deque a) shiftRight = reader Deque.shiftRight  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the elements satisfying the predicate. -} filter :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) filter predicate = reader (Deque.filter predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the specified amount of first elements. -} take :: MonadReader (Deque a) m => Int -> m (Deque a) take = reader . Deque.take  {-|-/O(n)/.+\(\mathcal{O}(n)\). Drop the specified amount of first elements. -} drop :: MonadReader (Deque a) m => Int -> m (Deque a) drop = reader . Deque.drop  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the first elements satisfying the predicate. -} takeWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) takeWhile predicate = reader (Deque.takeWhile predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Drop the first elements satisfying the predicate. -} dropWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a) dropWhile predicate = reader (Deque.dropWhile predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Same as @(,) '<$>' `takeWhile` predicate '<*>' `dropWhile` predicate@. -} span :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a, Deque a) span predicate = reader (Deque.span predicate)  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{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)@@ -118,7 +118,7 @@   Just (a, newDeque) -> (Just a, newDeque))  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{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)@@ -127,42 +127,42 @@   Just (a, newDeque) -> (Just a, newDeque))  {-|-/O(1)/. +\(\mathcal{O}(1)\).  Check whether deque is empty. -} null :: MonadReader (Deque a) m => m Bool null = reader Deque.null  {-|-/O(1)/. +\(\mathcal{O}(1)\).  Check whether deque is empty. -} length :: MonadReader (Deque a) m => m Int length = reader Prelude.length  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the first element if deque is not empty. -} head :: MonadReader (Deque a) m => m (Maybe a) head = reader Deque.head  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the last element if deque is not empty. -} last :: MonadReader (Deque a) m => m (Maybe a) last = reader Deque.last  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Keep all elements but the first one. -} tail :: MonadReader (Deque a) m => m (Deque a) tail = reader Deque.tail  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Keep all elements but the last one. -} init :: MonadReader (Deque a) m => m (Deque a)

@@ -11,105 +11,105 @@   {-|-/O(n)/.+\(\mathcal{O}(n)\). Modify each element of the queue. -} map :: MonadState (Deque a) m => (a -> a) -> m () map f = modify (fmap f)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Add elements to the begginning. -} prepend :: MonadState (Deque a) m => Deque a -> m () prepend deque = modify (deque <>)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Add elements to the ending. -} append :: MonadState (Deque a) m => Deque a -> m () append deque = modify (<> deque)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Add element in the beginning. -} cons :: MonadState (Deque a) m => a -> m () cons a = modify (Deque.cons a)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Add element in the ending. -} snoc :: MonadState (Deque a) m => a -> m () snoc a = modify (Deque.snoc a)  {-|-/O(1)/.+\(\mathcal{O}(1)\). Reverse the deque. -} reverse :: MonadState (Deque a) m => m () reverse = modify Deque.reverse  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Move the first element to the end. -} shiftLeft :: MonadState (Deque a) m => m () shiftLeft = modify Deque.shiftLeft  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Move the last element to the beginning. -} shiftRight :: MonadState (Deque a) m => m () shiftRight = modify Deque.shiftRight  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the elements satisfying the predicate. -} filter :: MonadState (Deque a) m => (a -> Bool) -> m () filter predicate = modify (Deque.filter predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the specified amount of first elements. -} take :: MonadState (Deque a) m => Int -> m () take = modify . Deque.take  {-|-/O(n)/.+\(\mathcal{O}(n)\). Drop the specified amount of first elements. -} drop :: MonadState (Deque a) m => Int -> m () drop = modify . Deque.drop  {-|-/O(n)/.+\(\mathcal{O}(n)\). Leave only the first elements satisfying the predicate. -} takeWhile :: MonadState (Deque a) m => (a -> Bool) -> m () takeWhile predicate = modify (Deque.takeWhile predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Drop the first elements satisfying the predicate. -} dropWhile :: MonadState (Deque a) m => (a -> Bool) -> m () dropWhile predicate = modify (Deque.dropWhile predicate)  {-|-/O(n)/.+\(\mathcal{O}(n)\). Return the first elements satisfying the predicate, removing them from the state. -} span :: MonadState (Deque a) m => (a -> Bool) -> m (Deque a) span predicate = state (Deque.span predicate)  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the first element if deque is not empty, removing the element. -}@@ -119,7 +119,7 @@   Just (a, newDeque) -> (Just a, newDeque))  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the last element if deque is not empty, removing the element. -}@@ -129,42 +129,42 @@   Just (a, newDeque) -> (Just a, newDeque))  {-|-/O(1)/. +\(\mathcal{O}(1)\).  Check whether deque is empty. -} null :: MonadState (Deque a) m => m Bool null = gets Deque.null  {-|-/O(1)/. +\(\mathcal{O}(1)\).  Check whether deque is empty. -} length :: MonadState (Deque a) m => m Int length = gets Prelude.length  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the first element if deque is not empty. -} head :: MonadState (Deque a) m => m (Maybe a) head = gets Deque.head  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Get the last element if deque is not empty. -} last :: MonadState (Deque a) m => m (Maybe a) last = gets Deque.last  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Keep all elements but the first one. -} tail :: MonadState (Deque a) m => m () tail = modify Deque.tail  {-|-/O(1)/, occasionally /O(n)/.+\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). Keep all elements but the last one. -} init :: MonadState (Deque a) m => m ()