deque 0.3 → 0.3.1

raw patch · 5 files changed

+189/−270 lines, 5 filesdep +strict-listPVP ok

version bump matches the API change (PVP)

Dependencies added: strict-list

API changes (from Hackage documentation)

Files

• deque.cabal +3/−3
• library/Deque/Lazy/State.hs +89/−52
• library/Deque/Strict.hs +8/−8
• library/Deque/Strict/State.hs +89/−52
• library/Deque/StrictList.hs +0/−155

@@ -1,5 +1,5 @@ name: deque-version: 0.3+version: 0.3.1 synopsis: Double-ended queues description:   Strict and lazy implementations of Double-Ended Queue (aka Dequeue or Deque)@@ -29,10 +29,10 @@     Deque.Strict.State   other-modules:     Deque.Prelude-    Deque.StrictList   build-depends:     base >=4.9 && <5,-    mtl >=2.2 && <3+    mtl >=2.2 && <3,+    strict-list >=0.1 && <0.2  test-suite test   type: exitcode-stdio-1.0

@@ -10,106 +10,143 @@ import qualified Deque.Prelude as Prelude  --- |--- /O(1)/.--- Add element in the beginning.+{-|+/O(n)/.+Modify each element of the queue.+-}+map :: MonadState (Deque a) m => (a -> a) -> m ()+map f = modify (fmap f)++{-|+/O(n)/.+Add elements from the begginning.+-}+prepend :: MonadState (Deque a) m => Deque a -> m ()+prepend deque = modify (deque <>)++{-|+/O(n)/.+Add elements from the ending.+-}+append :: MonadState (Deque a) m => Deque a -> m ()+append deque = modify (<> deque)++{-|+/O(1)/.+Add element in the beginning.+-} cons :: MonadState (Deque a) m => a -> m () cons a = modify (Deque.cons a) --- |--- /O(1)/.--- Add element in the ending.+{-|+/O(1)/.+Add element in the ending.+-} snoc :: MonadState (Deque a) m => a -> m () snoc a = modify (Deque.snoc a) --- |--- /O(1)/.--- Revert the deque.+{-|+/O(1)/.+Revert the deque.+-} reverse :: MonadState (Deque a) m => m () reverse = modify Deque.reverse --- |--- /O(1)/, occasionally /O(n)/.--- Move the first element to the end.+{-|+/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)/.--- Move the last element to the beginning.+{-|+/O(1)/, occasionally /O(n)/.+Move the last element to the beginning.+-} shiftRight :: MonadState (Deque a) m => m () shiftRight = modify Deque.shiftRight --- |--- /O(n)/.--- Leave only the elements satisfying the predicate.+{-|+/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)/.--- Leave only the first elements satisfying the predicate.+{-|+/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)/.--- Drop the first elements satisfying the predicate.+{-|+/O(n)/.+Drop the first elements satisfying the predicate.+-} dropWhile :: MonadState (Deque a) m => (a -> Bool) -> m () dropWhile predicate = modify (Deque.dropWhile predicate) --- |--- /O(1)/, occasionally /O(n)/.--- Get the first element and deque without it if it's not empty.+{-|+/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) uncons = state (\ deque -> case Deque.uncons deque of   Nothing -> (Nothing, deque)   Just (a, newDeque) -> (Just a, newDeque)) --- |--- /O(1)/, occasionally /O(n)/.--- Get the last element and deque without it if it's not empty.+{-|+/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) unsnoc = state (\ deque -> case Deque.unsnoc deque of   Nothing -> (Nothing, deque)   Just (a, newDeque) -> (Just a, newDeque)) --- |--- /O(1)/. --- Check whether deque is empty.+{-|+/O(1)/. +Check whether deque is empty.+-} null :: MonadState (Deque a) m => m Bool null = gets Deque.null --- |--- /O(1)/. --- Check whether deque is empty.+{-|+/O(1)/. +Check whether deque is empty.+-} length :: MonadState (Deque a) m => m Int length = gets Prelude.length --- |--- /O(1)/, occasionally /O(n)/.--- Get the first element if deque is not empty.+{-|+/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)/.--- Get the last element if deque is not empty.+{-|+/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)/.--- Keep all elements but the first one.--- --- In case of empty deque returns an empty deque.+{-|+/O(1)/, occasionally /O(n)/.+Keep all elements but the first one.++In case of empty deque returns an empty deque.+-} tail :: MonadState (Deque a) m => m (Deque a) tail = gets Deque.tail --- |--- /O(1)/, occasionally /O(n)/.--- Keep all elements but the last one.--- --- In case of empty deque returns an empty deque.+{-|+/O(1)/, occasionally /O(n)/.+Keep all elements but the last one.++In case of empty deque returns an empty deque.+-} init :: MonadState (Deque a) m => m (Deque a) init = gets Deque.init

@@ -28,14 +28,14 @@  import Control.Monad (fail) import Deque.Prelude hiding (tail, init, last, head, null, dropWhile, takeWhile, reverse, filter)-import qualified Deque.StrictList as StrictList+import qualified StrictList  -- | -- Strict double-ended queue (aka Dequeue or Deque) based on head-tail linked list. data Deque a = Deque {-# UNPACK #-} !(StrictList.List a) {-# UNPACK #-} !(StrictList.List a)  -- |--- /O(1)/.+-- /O(n)/. -- Construct from cons and snoc lists. fromConsAndSnocLists :: [a] -> [a] -> Deque a fromConsAndSnocLists consList snocList = Deque (fromList snocList) (fromList consList)@@ -86,8 +86,8 @@ filter :: (a -> Bool) -> Deque a -> Deque a filter predicate (Deque snocList consList) = let   newConsList = StrictList.prependReversed-    (StrictList.filterReverse predicate consList)-    (StrictList.filterReverse predicate snocList)+    (StrictList.filterReversed predicate consList)+    (StrictList.filterReversed predicate snocList)   in Deque StrictList.Nil newConsList  -- |@@ -164,7 +164,7 @@ -- In case of empty deque returns an empty deque. tail :: Deque a -> Deque a tail (Deque snocList consList) = case consList of-  StrictList.Nil -> Deque StrictList.Nil (StrictList.reverseInit snocList)+  StrictList.Nil -> Deque StrictList.Nil (StrictList.initReversed snocList)   _ -> Deque snocList (StrictList.tail consList)  -- |@@ -174,7 +174,7 @@ -- In case of empty deque returns an empty deque. init :: Deque a -> Deque a init (Deque snocList consList) = case snocList of-  StrictList.Nil -> Deque (StrictList.reverseInit consList) StrictList.Nil+  StrictList.Nil -> Deque (StrictList.initReversed consList) StrictList.Nil   _ -> Deque (StrictList.tail snocList) consList  @@ -186,8 +186,8 @@  instance IsList (Deque a) where   type Item (Deque a) = a-  fromList list = Deque (StrictList.fromReverseList list) StrictList.Nil-  toList (Deque snocList consList) = foldr (:) (StrictList.toReverseList snocList) consList+  fromList list = Deque (StrictList.fromListReversed list) StrictList.Nil+  toList (Deque snocList consList) = foldr (:) (toList (StrictList.reverse snocList)) consList  instance Semigroup (Deque a) where   (<>) (Deque snocList1 consList1) (Deque snocList2 consList2) = let

@@ -10,106 +10,143 @@ import qualified Deque.Prelude as Prelude  --- |--- /O(1)/.--- Add element in the beginning.+{-|+/O(n)/.+Modify each element of the queue.+-}+map :: MonadState (Deque a) m => (a -> a) -> m ()+map f = modify (fmap f)++{-|+/O(n)/.+Add elements from the begginning.+-}+prepend :: MonadState (Deque a) m => Deque a -> m ()+prepend deque = modify (deque <>)++{-|+/O(n)/.+Add elements from the ending.+-}+append :: MonadState (Deque a) m => Deque a -> m ()+append deque = modify (<> deque)++{-|+/O(1)/.+Add element in the beginning.+-} cons :: MonadState (Deque a) m => a -> m () cons a = modify (Deque.cons a) --- |--- /O(1)/.--- Add element in the ending.+{-|+/O(1)/.+Add element in the ending.+-} snoc :: MonadState (Deque a) m => a -> m () snoc a = modify (Deque.snoc a) --- |--- /O(1)/.--- Revert the deque.+{-|+/O(1)/.+Revert the deque.+-} reverse :: MonadState (Deque a) m => m () reverse = modify Deque.reverse --- |--- /O(1)/, occasionally /O(n)/.--- Move the first element to the end.+{-|+/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)/.--- Move the last element to the beginning.+{-|+/O(1)/, occasionally /O(n)/.+Move the last element to the beginning.+-} shiftRight :: MonadState (Deque a) m => m () shiftRight = modify Deque.shiftRight --- |--- /O(n)/.--- Leave only the elements satisfying the predicate.+{-|+/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)/.--- Leave only the first elements satisfying the predicate.+{-|+/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)/.--- Drop the first elements satisfying the predicate.+{-|+/O(n)/.+Drop the first elements satisfying the predicate.+-} dropWhile :: MonadState (Deque a) m => (a -> Bool) -> m () dropWhile predicate = modify (Deque.dropWhile predicate) --- |--- /O(1)/, occasionally /O(n)/.--- Get the first element and deque without it if it's not empty.+{-|+/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) uncons = state (\ deque -> case Deque.uncons deque of   Nothing -> (Nothing, deque)   Just (a, newDeque) -> (Just a, newDeque)) --- |--- /O(1)/, occasionally /O(n)/.--- Get the last element and deque without it if it's not empty.+{-|+/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) unsnoc = state (\ deque -> case Deque.unsnoc deque of   Nothing -> (Nothing, deque)   Just (a, newDeque) -> (Just a, newDeque)) --- |--- /O(1)/. --- Check whether deque is empty.+{-|+/O(1)/. +Check whether deque is empty.+-} null :: MonadState (Deque a) m => m Bool null = gets Deque.null --- |--- /O(1)/. --- Check whether deque is empty.+{-|+/O(1)/. +Check whether deque is empty.+-} length :: MonadState (Deque a) m => m Int length = gets Prelude.length --- |--- /O(1)/, occasionally /O(n)/.--- Get the first element if deque is not empty.+{-|+/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)/.--- Get the last element if deque is not empty.+{-|+/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)/.--- Keep all elements but the first one.--- --- In case of empty deque returns an empty deque.+{-|+/O(1)/, occasionally /O(n)/.+Keep all elements but the first one.++In case of empty deque returns an empty deque.+-} tail :: MonadState (Deque a) m => m (Deque a) tail = gets Deque.tail --- |--- /O(1)/, occasionally /O(n)/.--- Keep all elements but the last one.--- --- In case of empty deque returns an empty deque.+{-|+/O(1)/, occasionally /O(n)/.+Keep all elements but the last one.++In case of empty deque returns an empty deque.+-} init :: MonadState (Deque a) m => m (Deque a) init = gets Deque.init

@@ -1,155 +0,0 @@-module Deque.StrictList where--import Deque.Prelude hiding (takeWhile, dropWhile, reverse)---data List a = Cons !a !(List a) | Nil deriving-  (Eq, Ord, Show, Read, Foldable, Traversable, Generic, Generic1, Data, Typeable)--instance IsList (List a) where-  type Item (List a) = a-  fromList = reverse . fromReverseList-  toList = \ case-    Cons head tail -> head : toList tail-    _ -> []--instance Semigroup (List a) where-  (<>) a = prependReversed (reverse a)--instance Monoid (List a) where-  mempty = Nil-  mappend = (<>)--instance Functor List where-  fmap f = reverse . mapReverse f--instance Applicative List where-  pure a = Cons a Nil-  (<*>) fList aList = reverse (apReverse fList aList)--instance Alternative List where-  empty = mempty-  (<|>) = mappend--mapReverse :: (a -> b) -> List a -> List b-mapReverse f = let-  loop !newList = \ case-    Cons head tail -> loop (Cons (f head) newList) tail-    _ -> newList-  in loop Nil--apReverse :: List (a -> b) -> List a -> List b-apReverse = let-  loop bList = \ case-    Cons f fTail -> \ case-      Cons a aTail -> loop (Cons (f a) bList) fTail aTail-      _ -> bList-    _ -> const bList-  in loop Nil--filterReverse :: (a -> Bool) -> List a -> List a-filterReverse predicate = let-  loop !newList = \ case-    Cons head tail -> if predicate head-      then loop (Cons head newList) tail-      else loop newList tail-    Nil -> newList-  in loop Nil--filter :: (a -> Bool) -> List a -> List a-filter predicate = reverse . filterReverse predicate--takeWhile :: (a -> Bool) -> List a -> List a-takeWhile predicate = \ case-  Cons head tail -> if predicate head-    then Cons head (takeWhile predicate tail)-    else Nil-  Nil -> Nil--reverse :: List a -> List a-reverse = foldl' (\ newList a -> Cons a newList) Nil--dropWhile :: (a -> Bool) -> List a -> List a-dropWhile predicate = \ case-  Cons head tail -> if predicate head-    then dropWhile predicate tail-    else Cons head tail-  Nil -> Nil--{-|-Same as @(`takeWhile` predicate . `reverse`)@.-E.g., -->>> takeWhileFromEnding (> 2) (fromList [1,4,2,3,4,5])-fromList [5,4,3]--}-takeWhileFromEnding :: (a -> Bool) -> List a -> List a-takeWhileFromEnding predicate = foldl'-  (\ newList a -> if predicate a-    then Cons a newList-    else Nil)-  Nil--{-|-Same as @(`dropWhile` predicate . `reverse`)@.-E.g., -->>> dropWhileFromEnding (> 2) (fromList [1,4,2,3,4,5])-fromList [2,4,1]--}-dropWhileFromEnding :: (a -> Bool) -> List a -> List a-dropWhileFromEnding predicate = let-  loop confirmed unconfirmed = \ case-    Cons head tail -> if predicate head-      then loop confirmed (Cons head unconfirmed) tail-      else let-        !newConfirmed = Cons head unconfirmed-        in loop newConfirmed newConfirmed tail-    Nil -> confirmed-  in loop Nil Nil--prependReversed :: List a -> List a -> List a-prependReversed = \ case-  Cons head tail -> prependReversed tail . Cons head-  Nil -> id--head :: List a -> Maybe a-head = \ case-  Cons head _ -> Just head-  _ -> Nothing--last :: List a -> Maybe a-last = let-  loop previous = \ case-    Cons head tail -> loop (Just head) tail-    _ -> previous-  in loop Nothing--tail :: List a -> List a-tail = \ case-  Cons head tail -> tail-  Nil -> Nil--reverseInit :: List a -> List a-reverseInit = let-  loop !confirmed unconfirmed = \ case-    Cons head tail -> loop unconfirmed (Cons head unconfirmed) tail-    _ -> confirmed-  in loop Nil Nil--init :: List a -> List a-init = reverse . reverseInit--fromReverseList :: [a] -> List a-fromReverseList = let-  loop !acc = \ case-    head : tail -> loop (Cons head acc) tail-    _ -> acc-  in loop Nil--toReverseList :: List a -> [a]-toReverseList = let-  loop !list = \ case-    Cons head tail -> loop (head : list) tail-    _ -> list-  in loop []