deque 0.4.4.2 → 0.4.4.3
raw patch · 8 files changed
+160/−159 lines, 8 filesdep ~strict-listPVP ok
version bump matches the API change (PVP)
Dependency ranges changed: strict-list
API changes (from Hackage documentation)
Files
- deque.cabal +30/−30
- library/Deque/Lazy/Defs.hs +21/−21
- library/Deque/Lazy/Reader.hs +22/−22
- library/Deque/Lazy/State.hs +22/−22
- library/Deque/Prelude.hs +1/−0
- library/Deque/Strict/Defs.hs +20/−20
- library/Deque/Strict/Reader.hs +22/−22
- library/Deque/Strict/State.hs +22/−22
deque.cabal view
@@ -1,28 +1,27 @@ cabal-version: 3.0-name: deque-version: 0.4.4.2-synopsis: Double-ended queues+name: deque+version: 0.4.4.3+synopsis: Double-ended queues description: Strict and lazy implementations of Double-Ended Queue (aka Dequeue or Deque) based on head-tail linked list. -category: Data-homepage: https://github.com/nikita-volkov/deque-bug-reports: https://github.com/nikita-volkov/deque/issues-author: Nikita Volkov <nikita.y.volkov@mail.ru>-maintainer: Nikita Volkov <nikita.y.volkov@mail.ru>-copyright: (c) 2016, Nikita Volkov-license: MIT-license-file: LICENSE+category: Data+homepage: https://github.com/nikita-volkov/deque+bug-reports: https://github.com/nikita-volkov/deque/issues+author: Nikita Volkov <nikita.y.volkov@mail.ru>+maintainer: Nikita Volkov <nikita.y.volkov@mail.ru>+copyright: (c) 2016, Nikita Volkov+license: MIT+license-file: LICENSE source-repository head- type: git+ type: git location: https://github.com/nikita-volkov/deque library- hs-source-dirs: library+ hs-source-dirs: library default-extensions:- NoImplicitPrelude BangPatterns DeriveDataTypeable DeriveFunctor@@ -31,14 +30,15 @@ FlexibleContexts FlexibleInstances LambdaCase+ NoImplicitPrelude RankNTypes ScopedTypeVariables StandaloneDeriving TypeApplications TypeFamilies - ghc-options: -funbox-strict-fields- default-language: Haskell2010+ ghc-options: -funbox-strict-fields+ default-language: Haskell2010 exposed-modules: Deque.Lazy Deque.Lazy.Reader@@ -53,17 +53,16 @@ Deque.Strict.Defs build-depends:- , base >=4.9 && <5- , deepseq >=1.4.3 && <2- , hashable >=1.2 && <2- , mtl >=2.2 && <3- , strict-list >=0.1.6 && <0.2+ base >=4.9 && <5,+ deepseq >=1.4.3 && <2,+ hashable >=1.2 && <2,+ mtl >=2.2 && <3,+ strict-list >=1 && <1.1, test-suite test- type: exitcode-stdio-1.0- hs-source-dirs: test+ type: exitcode-stdio-1.0+ hs-source-dirs: test default-extensions:- NoImplicitPrelude BangPatterns DeriveDataTypeable DeriveFunctor@@ -72,16 +71,17 @@ FlexibleContexts FlexibleInstances LambdaCase+ NoImplicitPrelude RankNTypes ScopedTypeVariables StandaloneDeriving TypeApplications TypeFamilies - default-language: Haskell2010- main-is: Main.hs+ default-language: Haskell2010+ main-is: Main.hs build-depends:- , deque- , rerebase <2- , tasty >=0.12 && <2- , tasty-quickcheck >=0.9 && <0.12+ deque,+ rerebase <2,+ tasty >=0.12 && <2,+ tasty-quickcheck >=0.9 && <0.12,
library/Deque/Lazy/Defs.hs view
@@ -15,19 +15,19 @@ data Deque a = Deque ![a] ![a] -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Construct from cons and snoc lists. fromConsAndSnocLists :: [a] -> [a] -> Deque a fromConsAndSnocLists consList snocList = Deque consList snocList -- |--- \(\mathcal{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) -- |--- \(\mathcal{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 [] -- |--- \(\mathcal{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 -- |--- \(\mathcal{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 [] -- |--- \(\mathcal{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 -- |--- \(\mathcal{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) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Add element in the beginning. cons :: a -> Deque a -> Deque a cons a (Deque consList snocList) = Deque (a : consList) snocList -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Add element in the ending. snoc :: a -> Deque a -> Deque a snoc a (Deque consList snocList) = Deque consList (a : snocList) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{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 -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Reverse the deque. reverse :: Deque a -> Deque a reverse (Deque consList snocList) = Deque snocList consList -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Check whether deque is empty. null :: Deque a -> Bool null (Deque consList snocList) = List.null snocList && List.null consList -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{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 -- |--- \(\mathcal{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) -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Add elements to the begginning. prepend :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) prepend deque = reader (deque <>) -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Add elements to the ending. append :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) append deque = reader (<> deque) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Add element in the beginning. cons :: (MonadReader (Deque a) m) => a -> m (Deque a) cons a = reader (Deque.cons a) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Add element in the ending. snoc :: (MonadReader (Deque a) m) => a -> m (Deque a) snoc a = reader (Deque.snoc a) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Reverse the deque. reverse :: (MonadReader (Deque a) m) => m (Deque a) reverse = reader Deque.reverse -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{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) -- |--- \(\mathcal{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 -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Drop the specified amount of first elements. drop :: (MonadReader (Deque a) m) => Int -> m (Deque a) drop = reader . Deque.drop -- |--- \(\mathcal{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) -- |--- \(\mathcal{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) -- |--- \(\mathcal{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) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 @@ ) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 @@ ) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Check whether deque is empty. null :: (MonadReader (Deque a) m) => m Bool null = reader Deque.null -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Check whether deque is empty. length :: (MonadReader (Deque a) m) => m Int length = reader Prelude.length -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Modify each element of the queue. map :: (MonadState (Deque a) m) => (a -> a) -> m () map f = modify (fmap f) -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Add elements to the begginning. prepend :: (MonadState (Deque a) m) => Deque a -> m () prepend deque = modify (deque <>) -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Add elements to the ending. append :: (MonadState (Deque a) m) => Deque a -> m () append deque = modify (<> deque) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Add element in the beginning. cons :: (MonadState (Deque a) m) => a -> m () cons a = modify (Deque.cons a) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Add element in the ending. snoc :: (MonadState (Deque a) m) => a -> m () snoc a = modify (Deque.snoc a) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Reverse the deque. reverse :: (MonadState (Deque a) m) => m () reverse = modify Deque.reverse -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- \(\O(1)\), occasionally \(\O(n)\). -- Move the first element to the end. shiftLeft :: (MonadState (Deque a) m) => m () shiftLeft = modify Deque.shiftLeft -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- \(\O(1)\), occasionally \(\O(n)\). -- Move the last element to the beginning. shiftRight :: (MonadState (Deque a) m) => m () shiftRight = modify Deque.shiftRight -- |--- \(\mathcal{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) -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Leave only the specified amount of first elements. take :: (MonadState (Deque a) m) => Int -> m () take = modify . Deque.take -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Drop the specified amount of first elements. drop :: (MonadState (Deque a) m) => Int -> m () drop = modify . Deque.drop -- |--- \(\mathcal{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) -- |--- \(\mathcal{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) -- |--- \(\mathcal{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) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 @@ ) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 @@ ) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Check whether deque is empty. null :: (MonadState (Deque a) m) => m Bool null = gets Deque.null -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Check whether deque is empty. length :: (MonadState (Deque a) m) => m Int length = gets Prelude.length -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- \(\O(1)\), occasionally \(\O(n)\). -- Keep all elements but the first one. tail :: (MonadState (Deque a) m) => m () tail = modify Deque.tail -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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/Prelude.hs view
@@ -60,6 +60,7 @@ import GHC.Generics as Exports (Generic, Generic1) import GHC.IO.Exception as Exports import Numeric as Exports+import StrictList as Exports (StrictList) import System.Environment as Exports import System.Exit as Exports import System.IO as Exports
library/Deque/Strict/Defs.hs view
@@ -13,38 +13,38 @@ -- | -- Strict double-ended queue (aka Dequeue or Deque) based on head-tail linked list.-data Deque a = Deque !(StrictList.List a) !(StrictList.List a)+data Deque a = Deque !(StrictList a) !(StrictList a) -- |--- \(\mathcal{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) -- |--- \(\mathcal{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 -- |--- \(\mathcal{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) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Reverse the deque. {-# INLINE reverse #-} reverse :: Deque a -> Deque a reverse (Deque consList snocList) = Deque snocList consList -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- \(\O(1)\), occasionally \(\O(n)\). -- Move the last element to the beginning. -- -- @@@ -71,7 +71,7 @@ balanceLeft = error "TODO" -- |--- \(\mathcal{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 -- |--- \(\mathcal{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 -- |--- \(\mathcal{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 -- |--- \(\mathcal{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 -- |--- \(\mathcal{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 -- |--- \(\mathcal{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) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Check whether deque is empty. {-# INLINE null #-} null :: Deque a -> Bool@@ -199,7 +199,7 @@ _ -> False -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{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) -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Add elements to the begginning. prepend :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) prepend deque = reader (deque <>) -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Add elements to the ending. append :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) append deque = reader (<> deque) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Add element in the beginning. cons :: (MonadReader (Deque a) m) => a -> m (Deque a) cons a = reader (Deque.cons a) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Add element in the ending. snoc :: (MonadReader (Deque a) m) => a -> m (Deque a) snoc a = reader (Deque.snoc a) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Reverse the deque. reverse :: (MonadReader (Deque a) m) => m (Deque a) reverse = reader Deque.reverse -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{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) -- |--- \(\mathcal{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 -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Drop the specified amount of first elements. drop :: (MonadReader (Deque a) m) => Int -> m (Deque a) drop = reader . Deque.drop -- |--- \(\mathcal{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) -- |--- \(\mathcal{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) -- |--- \(\mathcal{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) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 @@ ) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 @@ ) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Check whether deque is empty. null :: (MonadReader (Deque a) m) => m Bool null = reader Deque.null -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Check whether deque is empty. length :: (MonadReader (Deque a) m) => m Int length = reader Prelude.length -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Modify each element of the queue. map :: (MonadState (Deque a) m) => (a -> a) -> m () map f = modify (fmap f) -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Add elements to the begginning. prepend :: (MonadState (Deque a) m) => Deque a -> m () prepend deque = modify (deque <>) -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Add elements to the ending. append :: (MonadState (Deque a) m) => Deque a -> m () append deque = modify (<> deque) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Add element in the beginning. cons :: (MonadState (Deque a) m) => a -> m () cons a = modify (Deque.cons a) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Add element in the ending. snoc :: (MonadState (Deque a) m) => a -> m () snoc a = modify (Deque.snoc a) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Reverse the deque. reverse :: (MonadState (Deque a) m) => m () reverse = modify Deque.reverse -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- \(\O(1)\), occasionally \(\O(n)\). -- Move the first element to the end. shiftLeft :: (MonadState (Deque a) m) => m () shiftLeft = modify Deque.shiftLeft -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- \(\O(1)\), occasionally \(\O(n)\). -- Move the last element to the beginning. shiftRight :: (MonadState (Deque a) m) => m () shiftRight = modify Deque.shiftRight -- |--- \(\mathcal{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) -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Leave only the specified amount of first elements. take :: (MonadState (Deque a) m) => Int -> m () take = modify . Deque.take -- |--- \(\mathcal{O}(n)\).+-- \(\O(n)\). -- Drop the specified amount of first elements. drop :: (MonadState (Deque a) m) => Int -> m () drop = modify . Deque.drop -- |--- \(\mathcal{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) -- |--- \(\mathcal{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) -- |--- \(\mathcal{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) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 @@ ) -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 @@ ) -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Check whether deque is empty. null :: (MonadState (Deque a) m) => m Bool null = gets Deque.null -- |--- \(\mathcal{O}(1)\).+-- \(\O(1)\). -- Check whether deque is empty. length :: (MonadState (Deque a) m) => m Int length = gets Prelude.length -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{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 -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- \(\O(1)\), occasionally \(\O(n)\). -- Keep all elements but the first one. tail :: (MonadState (Deque a) m) => m () tail = modify Deque.tail -- |--- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- \(\O(1)\), occasionally \(\O(n)\). -- Keep all elements but the last one. init :: (MonadState (Deque a) m) => m () init = modify Deque.init