deque 0.4.0.2 → 0.4.1

raw patch · 6 files changed

+44/−6 lines, 6 filesdep ~strict-listPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: strict-list

API changes (from Hackage documentation)

+ Deque.Lazy: span :: (a -> Bool) -> Deque a -> (Deque a, Deque a)

+ Deque.Strict: span :: (a -> Bool) -> Deque a -> (Deque a, Deque a)

Files

deque.cabal +2/−2
library/Deque/Lazy.hs +1/−0
library/Deque/Lazy/Defs.hs +17/−1
library/Deque/Strict.hs +1/−0
library/Deque/Strict/Defs.hs +17/−0
test/Main.hs +6/−3

deque.cabal view

@@ -1,5 +1,5 @@ name: deque-version: 0.4.0.2+version: 0.4.1 synopsis: Double-ended queues description:   Strict and lazy implementations of Double-Ended Queue (aka Dequeue or Deque)@@ -37,7 +37,7 @@   build-depends:     base >=4.9 && <5,     mtl >=2.2 && <3,-    strict-list >=0.1 && <0.2+    strict-list >=0.1.4 && <0.2  test-suite test   type: exitcode-stdio-1.0

library/Deque/Lazy.hs view

@@ -20,6 +20,7 @@   LazyDefs.drop,   LazyDefs.takeWhile,   LazyDefs.dropWhile,+  LazyDefs.span,   LazyDefs.uncons,   LazyDefs.unsnoc,   LazyDefs.null,

library/Deque/Lazy/Defs.hs view

@@ -88,6 +88,22 @@     _ -> Deque newConsList snocList  -- |+-- /O(n)/.+-- Same as @(`takeWhile` predicate, `dropWhile` predicate)@.+span :: (a -> Bool) -> Deque a -> (Deque a, Deque a)+span predicate (Deque consList snocList) = case List.span predicate consList of+  (consPrefix, consSuffix) -> if List.null consSuffix+    then case List.span predicate (List.reverse snocList) of+      (snocPrefix, snocSuffix) -> let+        prefix = Deque (consPrefix <> snocPrefix) []+        suffix = Deque snocSuffix []+        in (prefix, suffix)+    else let+      prefix = Deque consPrefix []+      suffix = Deque consSuffix snocList+      in (prefix, suffix)++-- | -- /O(1)/, occasionally /O(n)/. -- Move the first element to the end. --@@ -230,7 +246,7 @@   (>>=) (Deque aConsList aSnocList) k = let     consList = let       aStep a accBConsList = case k a of-        Deque bConsList bSnocList -> bConsList <> List.reverse bSnocList <> accBConsList+        Deque bConsList bSnocList -> bConsList <> foldl' (flip (:)) accBConsList bSnocList       in foldr aStep (foldr aStep [] (List.reverse aSnocList)) aConsList     in Deque consList []   fail = const mempty

library/Deque/Strict.hs view

@@ -20,6 +20,7 @@   StrictDefs.drop,   StrictDefs.takeWhile,   StrictDefs.dropWhile,+  StrictDefs.span,   StrictDefs.uncons,   StrictDefs.unsnoc,   StrictDefs.null,

library/Deque/Strict/Defs.hs view

@@ -10,6 +10,7 @@ import Control.Monad (fail) import Deque.Prelude hiding (tail, init, last, head, null, dropWhile, takeWhile, reverse, filter, take) import qualified StrictList+import qualified Deque.Prelude as Prelude  -- | -- Strict double-ended queue (aka Dequeue or Deque) based on head-tail linked list.@@ -129,6 +130,22 @@   in case newConsList of     StrictList.Nil -> Deque (StrictList.dropWhileFromEnding predicate snocList) StrictList.Nil     _ -> Deque newConsList snocList++-- |+-- /O(n)/.+-- Same as @(`takeWhile` predicate, `dropWhile` predicate)@.+span :: (a -> Bool) -> Deque a -> (Deque a, Deque a)+span predicate (Deque consList snocList) = case StrictList.spanReversed predicate consList of+  (consReversedPrefix, consSuffix) -> if Prelude.null consSuffix+    then case StrictList.spanFromEnding predicate snocList of+      (snocPrefix, snocSuffix) -> let+        prefix = Deque (StrictList.prependReversed consReversedPrefix snocPrefix) StrictList.Nil+        suffix = Deque snocSuffix StrictList.Nil+        in (prefix, suffix)+    else let+      prefix = Deque StrictList.Nil consReversedPrefix+      suffix = Deque consSuffix snocList+      in (prefix, suffix)  -- | -- /O(1)/, occasionally /O(n)/.

test/Main.hs view

@@ -21,13 +21,13 @@     testImplementation "Strict"       toList fromList Strict.fromConsAndSnocLists       Strict.cons Strict.snoc Strict.reverse-      Strict.shiftLeft Strict.shiftRight Strict.filter Strict.take Strict.drop Strict.takeWhile Strict.dropWhile+      Strict.shiftLeft Strict.shiftRight Strict.filter Strict.take Strict.drop Strict.takeWhile Strict.dropWhile Strict.span       Strict.uncons Strict.unsnoc Strict.null Strict.head Strict.last Strict.tail Strict.init     ,     testImplementation "Lazy"       toList fromList Lazy.fromConsAndSnocLists       Lazy.cons Lazy.snoc Lazy.reverse-      Lazy.shiftLeft Lazy.shiftRight Lazy.filter Lazy.take Lazy.drop Lazy.takeWhile Lazy.dropWhile+      Lazy.shiftLeft Lazy.shiftRight Lazy.filter Lazy.take Lazy.drop Lazy.takeWhile Lazy.dropWhile Lazy.span       Lazy.uncons Lazy.unsnoc Lazy.null Lazy.head Lazy.last Lazy.tail Lazy.init     ,     testGroup "Conversions" $@@ -58,7 +58,7 @@ testImplementation name   (toList :: forall a. f a -> [a]) fromList fromConsAndSnocLists   cons snoc reverse-  shiftLeft shiftRight filter take drop takeWhile dropWhile+  shiftLeft shiftRight filter take drop takeWhile dropWhile span   uncons unsnoc null head last tail init =     testGroup ("Deque implementation: " <> name) $     [@@ -105,6 +105,9 @@       ,       testProperty "dropWhile" $ forAll ((,) <$> predicateGen <*> dequeAndListGen) $ \ (predicate, (deque, list)) ->       toList (dropWhile predicate deque) === List.dropWhile predicate list+      ,+      testProperty "span" $ forAll ((,) <$> predicateGen <*> dequeAndListGen) $ \ (predicate, (deque, list)) ->+      bimap toList toList (span predicate deque) === List.span predicate list       ,       testProperty "uncons" $ forAll dequeAndListGen $ \ (deque, list) ->       fmap (fmap toList) (uncons deque) === List.uncons list