deque 0.4.4.3 → 0.4.4.4

raw patch · 7 files changed

+129/−129 lines, 7 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

deque.cabal +1/−1
library/Deque/Lazy/Defs.hs +21/−21
library/Deque/Lazy/Reader.hs +22/−22
library/Deque/Lazy/State.hs +22/−22
library/Deque/Strict/Defs.hs +19/−19
library/Deque/Strict/Reader.hs +22/−22
library/Deque/Strict/State.hs +22/−22

deque.cabal view

@@ -1,6 +1,6 @@ cabal-version: 3.0 name: deque-version: 0.4.4.3+version: 0.4.4.4 synopsis: Double-ended queues description:   Strict and lazy implementations of Double-Ended Queue (aka Dequeue or Deque)

library/Deque/Lazy/Defs.hs view

@@ -15,19 +15,19 @@ data Deque a = Deque ![a] ![a]  -- |--- \(\O(1)\).+-- \(O(1)\). -- Construct from cons and snoc lists. fromConsAndSnocLists :: [a] -> [a] -> Deque a fromConsAndSnocLists consList snocList = Deque consList snocList  -- |--- \(\O(n)\).+-- \(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)\).+-- \(O(n)\). -- Leave only the specified amount of first elements. take :: Int -> Deque a -> Deque a take amount (Deque consList snocList) =@@ -48,7 +48,7 @@    in Deque newConsList []  -- |--- \(\O(n)\).+-- \(O(n)\). -- Drop the specified amount of first elements. drop :: Int -> Deque a -> Deque a drop amount (Deque consList snocList) =@@ -67,7 +67,7 @@    in buildFromConsList amount consList  -- |--- \(\O(n)\).+-- \(O(n)\). -- Leave only the first elements satisfying the predicate. takeWhile :: (a -> Bool) -> Deque a -> Deque a takeWhile predicate (Deque consList snocList) =@@ -83,7 +83,7 @@    in Deque newConsList []  -- |--- \(\O(n)\).+-- \(O(n)\). -- Drop the first elements satisfying the predicate. dropWhile :: (a -> Bool) -> Deque a -> Deque a dropWhile predicate (Deque consList snocList) =@@ -93,7 +93,7 @@         _ -> Deque newConsList snocList  -- |--- \(\O(n)\).+-- \(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@@ -110,7 +110,7 @@          in (prefix, suffix)  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Move the first element to the end. -- -- @@@ -121,7 +121,7 @@ shiftLeft deque = maybe deque (uncurry snoc) (uncons deque)  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Move the last element to the beginning. -- -- @@@ -132,19 +132,19 @@ shiftRight deque = maybe deque (uncurry cons) (unsnoc deque)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Add element in the beginning. cons :: a -> Deque a -> Deque a cons a (Deque consList snocList) = Deque (a : consList) snocList  -- |--- \(\O(1)\).+-- \(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)\).+-- \(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) uncons (Deque consList snocList) = case consList of@@ -154,7 +154,7 @@     _ -> Nothing  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(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) unsnoc (Deque consList snocList) = case snocList of@@ -164,7 +164,7 @@     _ -> Nothing  -- |--- \(\O(n)\).+-- \(O(n)\). prepend :: Deque a -> Deque a -> Deque a prepend (Deque consList1 snocList1) (Deque consList2 snocList2) =   let consList = consList1@@ -172,25 +172,25 @@    in Deque consList snocList  -- |--- \(\O(1)\).+-- \(O(1)\). -- Reverse the deque. reverse :: Deque a -> Deque a reverse (Deque consList snocList) = Deque snocList consList  -- |--- \(\O(1)\).+-- \(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)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(O(n)\). -- Keep all elements but the first one. -- -- In case of empty deque returns an empty deque.@@ -198,7 +198,7 @@ tail = fromMaybe <$> id <*> fmap snd . uncons  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Keep all elements but the last one. -- -- In case of empty deque returns an empty deque.@@ -206,7 +206,7 @@ init = fromMaybe <$> id <*> fmap snd . unsnoc  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Get the last element if deque is not empty. last :: Deque a -> Maybe a last = fmap fst . unsnoc@@ -270,7 +270,7 @@   fail = const mempty  -- |--- \(\O(1)\).+-- \(O(1)\). instance IsList (Deque a) where   type Item (Deque a) = a   fromList = flip Deque []

library/Deque/Lazy/Reader.hs view

@@ -8,91 +8,91 @@ import qualified Deque.Prelude as Prelude  -- |--- \(\O(n)\).+-- \(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)\).+-- \(O(n)\). -- Add elements to the begginning. prepend :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) prepend deque = reader (deque <>)  -- |--- \(\O(n)\).+-- \(O(n)\). -- Add elements to the ending. append :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) append deque = reader (<> deque)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Add element in the beginning. cons :: (MonadReader (Deque a) m) => a -> m (Deque a) cons a = reader (Deque.cons a)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Add element in the ending. snoc :: (MonadReader (Deque a) m) => a -> m (Deque a) snoc a = reader (Deque.snoc a)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Reverse the deque. reverse :: (MonadReader (Deque a) m) => m (Deque a) reverse = reader Deque.reverse  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(O(n)\). -- Move the last element to the beginning. shiftRight :: (MonadReader (Deque a) m) => m (Deque a) shiftRight = reader Deque.shiftRight  -- |--- \(\O(n)\).+-- \(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)\).+-- \(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)\).+-- \(O(n)\). -- Drop the specified amount of first elements. drop :: (MonadReader (Deque a) m) => Int -> m (Deque a) drop = reader . Deque.drop  -- |--- \(\O(n)\).+-- \(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)\).+-- \(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)\).+-- \(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)\).+-- \(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) uncons =@@ -103,7 +103,7 @@     )  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(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) unsnoc =@@ -114,37 +114,37 @@     )  -- |--- \(\O(1)\).+-- \(O(1)\). -- Check whether deque is empty. null :: (MonadReader (Deque a) m) => m Bool null = reader Deque.null  -- |--- \(\O(1)\).+-- \(O(1)\). -- Check whether deque is empty. length :: (MonadReader (Deque a) m) => m Int length = reader Prelude.length  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(O(n)\). -- Keep all elements but the last one. init :: (MonadReader (Deque a) m) => m (Deque a) init = reader Deque.init

library/Deque/Lazy/State.hs view

@@ -8,91 +8,91 @@ import qualified Deque.Prelude as Prelude  -- |--- \(\O(n)\).+-- \(O(n)\). -- Modify each element of the queue. map :: (MonadState (Deque a) m) => (a -> a) -> m () map f = modify (fmap f)  -- |--- \(\O(n)\).+-- \(O(n)\). -- Add elements to the begginning. prepend :: (MonadState (Deque a) m) => Deque a -> m () prepend deque = modify (deque <>)  -- |--- \(\O(n)\).+-- \(O(n)\). -- Add elements to the ending. append :: (MonadState (Deque a) m) => Deque a -> m () append deque = modify (<> deque)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Add element in the beginning. cons :: (MonadState (Deque a) m) => a -> m () cons a = modify (Deque.cons a)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Add element in the ending. snoc :: (MonadState (Deque a) m) => a -> m () snoc a = modify (Deque.snoc a)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Reverse the deque. reverse :: (MonadState (Deque a) m) => m () reverse = modify Deque.reverse  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Move the first element to the end. shiftLeft :: (MonadState (Deque a) m) => m () shiftLeft = modify Deque.shiftLeft  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Move the last element to the beginning. shiftRight :: (MonadState (Deque a) m) => m () shiftRight = modify Deque.shiftRight  -- |--- \(\O(n)\).+-- \(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)\).+-- \(O(n)\). -- Leave only the specified amount of first elements. take :: (MonadState (Deque a) m) => Int -> m () take = modify . Deque.take  -- |--- \(\O(n)\).+-- \(O(n)\). -- Drop the specified amount of first elements. drop :: (MonadState (Deque a) m) => Int -> m () drop = modify . Deque.drop  -- |--- \(\O(n)\).+-- \(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)\).+-- \(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)\).+-- \(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)\).+-- \(O(1)\), occasionally \(O(n)\). -- Get the first element if deque is not empty, -- removing the element. uncons :: (MonadState (Deque a) m) => m (Maybe a)@@ -104,7 +104,7 @@     )  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Get the last element if deque is not empty, -- removing the element. unsnoc :: (MonadState (Deque a) m) => m (Maybe a)@@ -116,37 +116,37 @@     )  -- |--- \(\O(1)\).+-- \(O(1)\). -- Check whether deque is empty. null :: (MonadState (Deque a) m) => m Bool null = gets Deque.null  -- |--- \(\O(1)\).+-- \(O(1)\). -- Check whether deque is empty. length :: (MonadState (Deque a) m) => m Int length = gets Prelude.length  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(O(n)\). -- Keep all elements but the first one. tail :: (MonadState (Deque a) m) => m () tail = modify Deque.tail  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Keep all elements but the last one. init :: (MonadState (Deque a) m) => m () init = modify Deque.init

library/Deque/Strict/Defs.hs view

@@ -16,35 +16,35 @@ data Deque a = Deque !(StrictList a) !(StrictList a)  -- |--- \(\O(n)\).+-- \(O(n)\). -- Construct from cons and snoc lists. {-# INLINE fromConsAndSnocLists #-} fromConsAndSnocLists :: [a] -> [a] -> Deque a fromConsAndSnocLists consList snocList = Deque (fromList consList) (fromList snocList)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Add element in the beginning. {-# INLINE cons #-} cons :: a -> Deque a -> Deque a cons a (Deque consList snocList) = Deque (StrictList.Cons a consList) snocList  -- |--- \(\O(1)\).+-- \(O(1)\). -- Add element in the ending. {-# INLINE snoc #-} snoc :: a -> Deque a -> Deque a snoc a (Deque consList snocList) = Deque consList (StrictList.Cons a snocList)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Reverse the deque. {-# INLINE reverse #-} reverse :: Deque a -> Deque a reverse (Deque consList snocList) = Deque snocList consList  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Move the first element to the end. -- -- @@@ -56,7 +56,7 @@ shiftLeft deque = maybe deque (uncurry snoc) (uncons deque)  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Move the last element to the beginning. -- -- @@@ -71,7 +71,7 @@ balanceLeft = error "TODO"  -- |--- \(\O(n)\).+-- \(O(n)\). -- Leave only the elements satisfying the predicate. {-# INLINE filter #-} filter :: (a -> Bool) -> Deque a -> Deque a@@ -83,7 +83,7 @@    in Deque newConsList StrictList.Nil  -- |--- \(\O(n)\).+-- \(O(n)\). -- Leave only the specified amount of first elements. take :: Int -> Deque a -> Deque a take amount (Deque consList snocList) =@@ -104,7 +104,7 @@    in Deque StrictList.Nil newSnocList  -- |--- \(\O(n)\).+-- \(O(n)\). -- Drop the specified amount of first elements. drop :: Int -> Deque a -> Deque a drop amount (Deque consList snocList) =@@ -123,7 +123,7 @@    in buildFromConsList amount consList  -- |--- \(\O(n)\).+-- \(O(n)\). -- Leave only the first elements satisfying the predicate. {-# INLINE takeWhile #-} takeWhile :: (a -> Bool) -> Deque a -> Deque a@@ -140,7 +140,7 @@    in Deque newConsList StrictList.Nil  -- |--- \(\O(n)\).+-- \(O(n)\). -- Drop the first elements satisfying the predicate. {-# INLINE dropWhile #-} dropWhile :: (a -> Bool) -> Deque a -> Deque a@@ -151,7 +151,7 @@         _ -> Deque newConsList snocList  -- |--- \(\O(n)\).+-- \(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@@ -168,7 +168,7 @@          in (prefix, suffix)  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Get the first element and deque without it if it's not empty. {-# INLINE uncons #-} uncons :: Deque a -> Maybe (a, Deque a)@@ -179,7 +179,7 @@     _ -> Nothing  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Get the last element and deque without it if it's not empty. {-# INLINE unsnoc #-} unsnoc :: Deque a -> Maybe (a, Deque a)@@ -190,7 +190,7 @@     _ -> Nothing  -- |--- \(\O(1)\).+-- \(O(1)\). -- Check whether deque is empty. {-# INLINE null #-} null :: Deque a -> Bool@@ -199,7 +199,7 @@   _ -> False  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Get the first element if deque is not empty. {-# INLINE head #-} head :: Deque a -> Maybe a@@ -208,7 +208,7 @@   _ -> StrictList.last snocList  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Get the last element if deque is not empty. {-# INLINE last #-} last :: Deque a -> Maybe a@@ -217,7 +217,7 @@   _ -> StrictList.last consList  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Keep all elements but the first one. -- -- In case of empty deque returns an empty deque.@@ -228,7 +228,7 @@   _ -> Deque (StrictList.initReversed snocList) StrictList.Nil  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Keep all elements but the last one. -- -- In case of empty deque returns an empty deque.

library/Deque/Strict/Reader.hs view

@@ -8,91 +8,91 @@ import qualified Deque.Strict as Deque  -- |--- \(\O(n)\).+-- \(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)\).+-- \(O(n)\). -- Add elements to the begginning. prepend :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) prepend deque = reader (deque <>)  -- |--- \(\O(n)\).+-- \(O(n)\). -- Add elements to the ending. append :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) append deque = reader (<> deque)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Add element in the beginning. cons :: (MonadReader (Deque a) m) => a -> m (Deque a) cons a = reader (Deque.cons a)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Add element in the ending. snoc :: (MonadReader (Deque a) m) => a -> m (Deque a) snoc a = reader (Deque.snoc a)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Reverse the deque. reverse :: (MonadReader (Deque a) m) => m (Deque a) reverse = reader Deque.reverse  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(O(n)\). -- Move the last element to the beginning. shiftRight :: (MonadReader (Deque a) m) => m (Deque a) shiftRight = reader Deque.shiftRight  -- |--- \(\O(n)\).+-- \(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)\).+-- \(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)\).+-- \(O(n)\). -- Drop the specified amount of first elements. drop :: (MonadReader (Deque a) m) => Int -> m (Deque a) drop = reader . Deque.drop  -- |--- \(\O(n)\).+-- \(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)\).+-- \(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)\).+-- \(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)\).+-- \(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) uncons =@@ -103,7 +103,7 @@     )  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(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) unsnoc =@@ -114,37 +114,37 @@     )  -- |--- \(\O(1)\).+-- \(O(1)\). -- Check whether deque is empty. null :: (MonadReader (Deque a) m) => m Bool null = reader Deque.null  -- |--- \(\O(1)\).+-- \(O(1)\). -- Check whether deque is empty. length :: (MonadReader (Deque a) m) => m Int length = reader Prelude.length  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(O(n)\). -- Keep all elements but the last one. init :: (MonadReader (Deque a) m) => m (Deque a) init = reader Deque.init

library/Deque/Strict/State.hs view

@@ -8,91 +8,91 @@ import qualified Deque.Strict as Deque  -- |--- \(\O(n)\).+-- \(O(n)\). -- Modify each element of the queue. map :: (MonadState (Deque a) m) => (a -> a) -> m () map f = modify (fmap f)  -- |--- \(\O(n)\).+-- \(O(n)\). -- Add elements to the begginning. prepend :: (MonadState (Deque a) m) => Deque a -> m () prepend deque = modify (deque <>)  -- |--- \(\O(n)\).+-- \(O(n)\). -- Add elements to the ending. append :: (MonadState (Deque a) m) => Deque a -> m () append deque = modify (<> deque)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Add element in the beginning. cons :: (MonadState (Deque a) m) => a -> m () cons a = modify (Deque.cons a)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Add element in the ending. snoc :: (MonadState (Deque a) m) => a -> m () snoc a = modify (Deque.snoc a)  -- |--- \(\O(1)\).+-- \(O(1)\). -- Reverse the deque. reverse :: (MonadState (Deque a) m) => m () reverse = modify Deque.reverse  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Move the first element to the end. shiftLeft :: (MonadState (Deque a) m) => m () shiftLeft = modify Deque.shiftLeft  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Move the last element to the beginning. shiftRight :: (MonadState (Deque a) m) => m () shiftRight = modify Deque.shiftRight  -- |--- \(\O(n)\).+-- \(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)\).+-- \(O(n)\). -- Leave only the specified amount of first elements. take :: (MonadState (Deque a) m) => Int -> m () take = modify . Deque.take  -- |--- \(\O(n)\).+-- \(O(n)\). -- Drop the specified amount of first elements. drop :: (MonadState (Deque a) m) => Int -> m () drop = modify . Deque.drop  -- |--- \(\O(n)\).+-- \(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)\).+-- \(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)\).+-- \(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)\).+-- \(O(1)\), occasionally \(O(n)\). -- Get the first element if deque is not empty, -- removing the element. uncons :: (MonadState (Deque a) m) => m (Maybe a)@@ -104,7 +104,7 @@     )  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Get the last element if deque is not empty, -- removing the element. unsnoc :: (MonadState (Deque a) m) => m (Maybe a)@@ -116,37 +116,37 @@     )  -- |--- \(\O(1)\).+-- \(O(1)\). -- Check whether deque is empty. null :: (MonadState (Deque a) m) => m Bool null = gets Deque.null  -- |--- \(\O(1)\).+-- \(O(1)\). -- Check whether deque is empty. length :: (MonadState (Deque a) m) => m Int length = gets Prelude.length  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(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)\).+-- \(O(1)\), occasionally \(O(n)\). -- Keep all elements but the first one. tail :: (MonadState (Deque a) m) => m () tail = modify Deque.tail  -- |--- \(\O(1)\), occasionally \(\O(n)\).+-- \(O(1)\), occasionally \(O(n)\). -- Keep all elements but the last one. init :: (MonadState (Deque a) m) => m () init = modify Deque.init