deque 0.3.1.1 → 0.4

raw patch · 11 files changed

+985/−462 lines, 11 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• deque.cabal +6/−1
• library/Deque/Lazy.hs +30/−213
• library/Deque/Lazy/Defs.hs +243/−0
• library/Deque/Lazy/Reader.hs +162/−0
• library/Deque/Lazy/State.hs +18/−8
• library/Deque/Prelude.hs +5/−1
• library/Deque/Strict.hs +30/−217
• library/Deque/Strict/Defs.hs +247/−0
• library/Deque/Strict/Reader.hs +162/−0
• library/Deque/Strict/State.hs +18/−8
• test/Main.hs +64/−14

@@ -1,5 +1,5 @@ name: deque-version: 0.3.1.1+version: 0.4 synopsis: Double-ended queues description:   Strict and lazy implementations of Double-Ended Queue (aka Dequeue or Deque)@@ -21,13 +21,18 @@ library   hs-source-dirs: library   default-extensions: BangPatterns, DeriveDataTypeable, DeriveGeneric, DeriveFunctor, DeriveTraversable, FlexibleContexts, FlexibleInstances, LambdaCase, NoImplicitPrelude, RankNTypes, ScopedTypeVariables, StandaloneDeriving, TypeApplications, TypeFamilies+  ghc-options: -funbox-strict-fields   default-language: Haskell2010   exposed-modules:     Deque.Lazy+    Deque.Lazy.Reader     Deque.Lazy.State     Deque.Strict+    Deque.Strict.Reader     Deque.Strict.State   other-modules:+    Deque.Lazy.Defs+    Deque.Strict.Defs     Deque.Prelude   build-depends:     base >=4.9 && <5,

@@ -6,221 +6,38 @@ -} module Deque.Lazy (-  Deque,-  fromConsAndSnocLists,-  cons,-  snoc,-  reverse,-  shiftLeft,-  shiftRight,-  filter,-  takeWhile,-  dropWhile,-  uncons,-  unsnoc,-  null,-  head,-  last,-  tail,-  init,+  LazyDefs.Deque,+  fromStrict,+  toStrict,+  LazyDefs.fromConsAndSnocLists,+  LazyDefs.cons,+  LazyDefs.snoc,+  LazyDefs.reverse,+  LazyDefs.shiftLeft,+  LazyDefs.shiftRight,+  LazyDefs.filter,+  LazyDefs.take,+  LazyDefs.drop,+  LazyDefs.takeWhile,+  LazyDefs.dropWhile,+  LazyDefs.uncons,+  LazyDefs.unsnoc,+  LazyDefs.null,+  LazyDefs.head,+  LazyDefs.last,+  LazyDefs.tail,+  LazyDefs.init, ) where -import Control.Monad (fail)-import Deque.Prelude hiding (tail, init, last, head, null, dropWhile, takeWhile, reverse, filter)-import qualified Data.List as List-import qualified Deque.Prelude as Prelude---- |--- Lazy double-ended queue (aka Dequeue or Deque) based on head-tail linked list.-data Deque a = Deque {-# UNPACK #-} ![a] {-# UNPACK #-} ![a]---- |--- /O(1)/.--- Construct from cons and snoc lists.-fromConsAndSnocLists :: [a] -> [a] -> Deque a-fromConsAndSnocLists consList snocList = Deque snocList consList---- |--- /O(n)/.--- Leave only the elements satisfying the predicate.-filter :: (a -> Bool) -> Deque a -> Deque a-filter predicate (Deque snocList consList) = Deque (List.filter predicate snocList) (List.filter predicate consList)---- |--- /O(n)/.--- Leave only the first elements satisfying the predicate.-takeWhile :: (a -> Bool) -> Deque a -> Deque a-takeWhile predicate (Deque snocList consList) = let-  newConsList = List.foldr-    (\ a nextState -> if predicate a-      then a : nextState-      else [])-    (List.takeWhile predicate (List.reverse snocList))-    consList-  in Deque [] newConsList---- |--- /O(n)/.--- Drop the first elements satisfying the predicate.-dropWhile :: (a -> Bool) -> Deque a -> Deque a-dropWhile predicate (Deque snocList consList) = let-  newConsList = List.dropWhile predicate consList-  in case newConsList of-    [] -> Deque [] (List.dropWhile predicate (List.reverse snocList))-    _ -> Deque snocList newConsList---- |--- /O(1)/, occasionally /O(n)/.--- Move the first element to the end.------ @--- λ toList . shiftLeft $ fromList [1,2,3]--- [2,3,1]--- @-shiftLeft :: Deque a -> Deque a-shiftLeft deque = maybe deque (uncurry snoc) (uncons deque)---- |--- /O(1)/, occasionally /O(n)/.--- Move the last element to the beginning.------ @--- λ toList . shiftRight $ fromList [1,2,3]--- [3,1,2]--- @-shiftRight :: Deque a -> Deque a-shiftRight deque = maybe deque (uncurry cons) (unsnoc deque)---- |--- /O(1)/.--- Add element in the beginning.-cons :: a -> Deque a -> Deque a-cons a (Deque snocList consList) = Deque snocList (a : consList)---- |--- /O(1)/.--- Add element in the ending.-snoc :: a -> Deque a -> Deque a-snoc a (Deque snocList consList) = Deque (a : snocList) consList---- |--- /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 snocList consList) = case consList of-  head : tail -> Just (head, Deque snocList tail)-  _ -> case List.reverse snocList of-    head : tail -> Just (head, Deque [] tail)-    _ -> Nothing---- |--- /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 snocList consList) = case snocList of-  head : tail -> Just (head, Deque tail consList)-  _ -> case List.reverse consList of-    head : tail -> Just (head, Deque tail [])-    _ -> Nothing---- |--- /O(n)/.-prepend :: Deque a -> Deque a -> Deque a-prepend (Deque snocList1 consList1) (Deque snocList2 consList2) = Deque snocList3 consList3 where-  snocList3 = snocList2 ++ foldl' (flip (:)) snocList1 consList2-  consList3 = consList1---- |--- /O(1)/.--- Reverse the deque.-reverse :: Deque a -> Deque a-reverse (Deque snocList consList) = Deque consList snocList---- |--- /O(1)/. --- Check whether deque is empty.-null :: Deque a -> Bool-null (Deque snocList consList) = List.null snocList && List.null consList---- |--- /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)/.--- Keep all elements but the first one.--- --- In case of empty deque returns an empty deque.-tail :: Deque a -> Deque a-tail = fromMaybe <$> id <*> fmap snd . uncons---- |--- /O(1)/, occasionally /O(n)/.--- Keep all elements but the last one.--- --- In case of empty deque returns an empty deque.-init :: Deque a -> Deque a-init = fromMaybe <$> id <*> fmap snd . unsnoc---- |--- /O(1)/, occasionally /O(n)/.--- Get the last element if deque is not empty.-last :: Deque a -> Maybe a-last = fmap fst . unsnoc---instance Eq a => Eq (Deque a) where-  (==) a b = toList a == toList b--instance Show a => Show (Deque a) where-  show = showString "fromList " . show . toList--instance Semigroup (Deque a) where-  (<>) = prepend--instance Monoid (Deque a) where-  mempty =-    Deque [] []-  mappend =-    (<>)--instance Foldable Deque where-  foldr step init (Deque snocList consList) = foldr step (foldl' (flip step) init snocList) consList-  foldl' step init (Deque snocList consList) = foldr' (flip step) (foldl' step init consList) snocList--instance Traversable Deque where-  traverse f (Deque ss cs) =-    (\cs' ss' -> Deque (List.reverse ss') cs') <$> traverse f cs <*> traverse f (List.reverse ss)--deriving instance Functor Deque--instance Applicative Deque where-  pure a = Deque [] [a]-  fs <*> as = fromList (toList fs <*> toList as)--instance Monad Deque where-  return = pure-  m >>= f = fromList (toList m >>= toList . f)-  fail = const mempty--instance Alternative Deque where-  empty = mempty-  (<|>) = mappend--instance MonadPlus Deque where-  mzero = empty-  mplus = (<|>)+import Deque.Prelude+import qualified Deque.Lazy.Defs as LazyDefs+import qualified Deque.Strict.Defs as StrictDefs -instance MonadFail Deque where-  fail = const mempty+{-| Convert strict deque to lazy deque. -}+fromStrict :: StrictDefs.Deque a -> LazyDefs.Deque a+fromStrict (StrictDefs.Deque consList snocList) = LazyDefs.Deque (toList consList) (toList snocList) --- |--- /O(1)/.-instance IsList (Deque a) where-  type Item (Deque a) = a-  fromList = Deque []-  toList (Deque snocList consList) = consList <> List.reverse snocList-  +{-| Convert lazy deque to strict deque. -}+toStrict :: LazyDefs.Deque a -> StrictDefs.Deque a+toStrict (LazyDefs.Deque consList snocList) = StrictDefs.Deque (fromList consList) (fromList snocList)

@@ -0,0 +1,243 @@+{-|+Definitions of lazy Deque.++The typical `toList` and `fromList` conversions are provided by means of+the `Foldable` and `IsList` instances.+-}+module Deque.Lazy.Defs+where++import Control.Monad (fail)+import Deque.Prelude hiding (tail, init, last, head, null, dropWhile, takeWhile, reverse, filter, take)+import qualified Data.List as List+import qualified Deque.Prelude as Prelude++-- |+-- Lazy double-ended queue (aka Dequeue or Deque) based on head-tail linked list.+data Deque a = Deque ![a] ![a]++-- |+-- /O(1)/.+-- Construct from cons and snoc lists.+fromConsAndSnocLists :: [a] -> [a] -> Deque a+fromConsAndSnocLists consList snocList = Deque consList snocList++-- |+-- /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)/.+-- Leave only the specified amount of first elements.+take :: Int -> Deque a -> Deque a+take amount (Deque consList snocList) = let+  newConsList = let+    buildFromConsList amount = if amount > 0+      then \ case+        head : tail -> head : buildFromConsList (pred amount) tail+        _ -> buildFromSnocList amount (List.reverse snocList)+      else const []+    buildFromSnocList amount = if amount > 0+      then \ case+        head : tail -> head : buildFromSnocList (pred amount) tail+        _ -> []+      else const []+    in buildFromConsList amount consList+  in Deque newConsList []++-- |+-- /O(n)/.+-- Drop the specified amount of first elements.+drop :: Int -> Deque a -> Deque a+drop amount (Deque consList snocList) = let+  buildFromConsList amount = if amount > 0+    then \ case+      _ : tail -> buildFromConsList (pred amount) tail+      _ -> buildFromSnocList amount (List.reverse snocList)+    else \ tail -> Deque tail snocList+  buildFromSnocList amount = if amount > 0+    then \ case+      _ : tail -> buildFromSnocList (pred amount) tail+      _ -> Deque [] []+    else \ tail -> Deque tail []+  in buildFromConsList amount consList++-- |+-- /O(n)/.+-- Leave only the first elements satisfying the predicate.+takeWhile :: (a -> Bool) -> Deque a -> Deque a+takeWhile predicate (Deque consList snocList) = let+  newConsList = List.foldr+    (\ a nextState -> if predicate a+      then a : nextState+      else [])+    (List.takeWhile predicate (List.reverse snocList))+    consList+  in Deque newConsList []++-- |+-- /O(n)/.+-- Drop the first elements satisfying the predicate.+dropWhile :: (a -> Bool) -> Deque a -> Deque a+dropWhile predicate (Deque consList snocList) = let+  newConsList = List.dropWhile predicate consList+  in case newConsList of+    [] -> Deque (List.dropWhile predicate (List.reverse snocList)) []+    _ -> Deque newConsList snocList++-- |+-- /O(1)/, occasionally /O(n)/.+-- Move the first element to the end.+--+-- @+-- λ toList . shiftLeft $ fromList [1,2,3]+-- [2,3,1]+-- @+shiftLeft :: Deque a -> Deque a+shiftLeft deque = maybe deque (uncurry snoc) (uncons deque)++-- |+-- /O(1)/, occasionally /O(n)/.+-- Move the last element to the beginning.+--+-- @+-- λ toList . shiftRight $ fromList [1,2,3]+-- [3,1,2]+-- @+shiftRight :: Deque a -> Deque a+shiftRight deque = maybe deque (uncurry cons) (unsnoc deque)++-- |+-- /O(1)/.+-- Add element in the beginning.+cons :: a -> Deque a -> Deque a+cons a (Deque consList snocList) = Deque (a : consList) snocList++-- |+-- /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)/.+-- 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+  head : tail -> Just (head, Deque tail snocList)+  _ -> case List.reverse snocList of+    head : tail -> Just (head, Deque tail [])+    _ -> Nothing++-- |+-- /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+  head : tail -> Just (head, Deque consList tail)+  _ -> case List.reverse consList of+    head : tail -> Just (head, Deque [] tail)+    _ -> Nothing++-- |+-- /O(n)/.+prepend :: Deque a -> Deque a -> Deque a+prepend (Deque snocList1 consList1) (Deque snocList2 consList2) = Deque consList3 snocList3 where+  consList3 = consList1+  snocList3 = snocList2 ++ foldl' (flip (:)) snocList1 consList2++-- |+-- /O(1)/.+-- Reverse the deque.+reverse :: Deque a -> Deque a+reverse (Deque consList snocList) = Deque snocList consList++-- |+-- /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)/.+-- Get the first element if deque is not empty.+head :: Deque a -> Maybe a+head = fmap fst . uncons++-- |+-- /O(1)/, occasionally /O(n)/.+-- Keep all elements but the first one.+-- +-- In case of empty deque returns an empty deque.+tail :: Deque a -> Deque a+tail = fromMaybe <$> id <*> fmap snd . uncons++-- |+-- /O(1)/, occasionally /O(n)/.+-- Keep all elements but the last one.+-- +-- In case of empty deque returns an empty deque.+init :: Deque a -> Deque a+init = fromMaybe <$> id <*> fmap snd . unsnoc++-- |+-- /O(1)/, occasionally /O(n)/.+-- Get the last element if deque is not empty.+last :: Deque a -> Maybe a+last = fmap fst . unsnoc+++instance Eq a => Eq (Deque a) where+  (==) a b = toList a == toList b++instance Show a => Show (Deque a) where+  show = show . toList++instance Semigroup (Deque a) where+  (<>) = prepend++instance Monoid (Deque a) where+  mempty =+    Deque [] []+  mappend =+    (<>)++instance Foldable Deque where+  foldr step init (Deque consList snocList) = foldr step (foldl' (flip step) init snocList) consList+  foldl' step init (Deque consList snocList) = foldr' (flip step) (foldl' step init consList) snocList++instance Traversable Deque where+  traverse f (Deque cs ss) =+    (\cs' ss' -> Deque cs' (List.reverse ss')) <$> traverse f cs <*> traverse f (List.reverse ss)++deriving instance Functor Deque++instance Applicative Deque where+  pure a = Deque [] [a]+  fs <*> as = fromList (toList fs <*> toList as)++instance Monad Deque where+  return = pure+  m >>= f = fromList (toList m >>= toList . f)+  fail = const mempty++instance Alternative Deque where+  empty = mempty+  (<|>) = mappend++instance MonadPlus Deque where+  mzero = empty+  mplus = (<|>)++instance MonadFail Deque where+  fail = const mempty++-- |+-- /O(1)/.+instance IsList (Deque a) where+  type Item (Deque a) = a+  fromList = flip Deque []+  toList (Deque consList snocList) = consList <> List.reverse snocList+  

@@ -0,0 +1,162 @@+{-|+Lazy Deque API lifted to a Reader monad, \"mtl\"-style.+-}+module Deque.Lazy.Reader+where++import Deque.Prelude hiding (tail, init, last, head, null, dropWhile, takeWhile, reverse)+import Deque.Lazy (Deque)+import qualified Deque.Lazy as Deque+import qualified Deque.Prelude as Prelude+++{-|+/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)/.+Add elements to the begginning.+-}+prepend :: MonadReader (Deque a) m => Deque a -> m (Deque a)+prepend deque = reader (deque <>)++{-|+/O(n)/.+Add elements to the ending.+-}+append :: MonadReader (Deque a) m => Deque a -> m (Deque a)+append deque = reader (<> deque)++{-|+/O(1)/.+Add element in the beginning.+-}+cons :: MonadReader (Deque a) m => a -> m (Deque a)+cons a = reader (Deque.cons a)++{-|+/O(1)/.+Add element in the ending.+-}+snoc :: MonadReader (Deque a) m => a -> m (Deque a)+snoc a = reader (Deque.snoc a)++{-|+/O(1)/.+Reverse the deque.+-}+reverse :: MonadReader (Deque a) m => m (Deque a)+reverse = reader Deque.reverse++{-|+/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)/.+Move the last element to the beginning.+-}+shiftRight :: MonadReader (Deque a) m => m (Deque a)+shiftRight = reader Deque.shiftRight++{-|+/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)/.+Leave only the specified amount of first elements.+-}+take :: MonadReader (Deque a) m => Int -> m (Deque a)+take = reader . Deque.take++{-|+/O(n)/.+Drop the specified amount of first elements.+-}+drop :: MonadReader (Deque a) m => Int -> m (Deque a)+drop = reader . Deque.drop++{-|+/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)/.+Drop the first elements satisfying the predicate.+-}+dropWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a)+dropWhile predicate = reader (Deque.dropWhile predicate)++{-|+/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 = reader (\ 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.+-}+unsnoc :: MonadReader (Deque a) m => m (Maybe a, Deque a)+unsnoc = reader (\ deque -> case Deque.unsnoc deque of+  Nothing -> (Nothing, deque)+  Just (a, newDeque) -> (Just a, newDeque))++{-|+/O(1)/. +Check whether deque is empty.+-}+null :: MonadReader (Deque a) m => m Bool+null = reader Deque.null++{-|+/O(1)/. +Check whether deque is empty.+-}+length :: MonadReader (Deque a) m => m Int+length = reader Prelude.length++{-|+/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)/.+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)/.+Keep all elements but the first one.+-}+tail :: MonadReader (Deque a) m => m (Deque a)+tail = reader Deque.tail++{-|+/O(1)/, occasionally /O(n)/.+Keep all elements but the last one.+-}+init :: MonadReader (Deque a) m => m (Deque a)+init = reader Deque.init

@@ -75,6 +75,20 @@  {-| /O(n)/.+Leave only the specified amount of first elements.+-}+take :: MonadState (Deque a) m => Int -> m ()+take = modify . Deque.take++{-|+/O(n)/.+Drop the specified amount of first elements.+-}+drop :: MonadState (Deque a) m => Int -> m ()+drop = modify . Deque.drop++{-|+/O(n)/. Leave only the first elements satisfying the predicate. -} takeWhile :: MonadState (Deque a) m => (a -> Bool) -> m ()@@ -136,17 +150,13 @@ {-| /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+tail :: MonadState (Deque a) m => m ()+tail = modify Deque.tail  {-| /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+init :: MonadState (Deque a) m => m ()+init = modify Deque.init

@@ -74,5 +74,9 @@  -- mtl --------------------------import Control.Monad.State.Strict as Exports hiding (fail)+import Control.Monad.Cont.Class as Exports hiding (fail)+import Control.Monad.Error.Class as Exports hiding (Error(..), fail)+import Control.Monad.Reader.Class as Exports hiding (fail)+import Control.Monad.State.Class as Exports hiding (fail)+import Control.Monad.Writer.Class as Exports hiding (fail) 

@@ -6,225 +6,38 @@ -} module Deque.Strict (-  Deque,-  fromConsAndSnocLists,-  cons,-  snoc,-  reverse,-  shiftLeft,-  shiftRight,-  filter,-  takeWhile,-  dropWhile,-  uncons,-  unsnoc,-  null,-  head,-  last,-  tail,-  init,+  StrictDefs.Deque,+  fromLazy,+  toLazy,+  StrictDefs.fromConsAndSnocLists,+  StrictDefs.cons,+  StrictDefs.snoc,+  StrictDefs.reverse,+  StrictDefs.shiftLeft,+  StrictDefs.shiftRight,+  StrictDefs.filter,+  StrictDefs.take,+  StrictDefs.drop,+  StrictDefs.takeWhile,+  StrictDefs.dropWhile,+  StrictDefs.uncons,+  StrictDefs.unsnoc,+  StrictDefs.null,+  StrictDefs.head,+  StrictDefs.last,+  StrictDefs.tail,+  StrictDefs.init, ) where -import Control.Monad (fail)-import Deque.Prelude hiding (tail, init, last, head, null, dropWhile, takeWhile, reverse, filter)-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(n)/.--- Construct from cons and snoc lists.-fromConsAndSnocLists :: [a] -> [a] -> Deque a-fromConsAndSnocLists consList snocList = Deque (fromList snocList) (fromList consList)---- |--- /O(1)/.--- Add element in the beginning.-cons :: a -> Deque a -> Deque a-cons a (Deque snocList consList) = Deque snocList (StrictList.Cons a consList)---- |--- /O(1)/.--- Add element in the ending.-snoc :: a -> Deque a -> Deque a-snoc a (Deque snocList consList) = Deque (StrictList.Cons a snocList) consList---- |--- /O(1)/.--- Reverse the deque.-reverse :: Deque a -> Deque a-reverse (Deque snocList consList) = Deque consList snocList---- |--- /O(1)/, occasionally /O(n)/.--- Move the first element to the end.------ @--- λ toList . shiftLeft $ fromList [1,2,3]--- [2,3,1]--- @-shiftLeft :: Deque a -> Deque a-shiftLeft deque = maybe deque (uncurry snoc) (uncons deque)---- |--- /O(1)/, occasionally /O(n)/.--- Move the last element to the beginning.------ @--- λ toList . shiftRight $ fromList [1,2,3]--- [3,1,2]--- @-shiftRight :: Deque a -> Deque a-shiftRight deque = maybe deque (uncurry cons) (unsnoc deque)---- |--- /O(n)/.--- Leave only the elements satisfying the predicate.-filter :: (a -> Bool) -> Deque a -> Deque a-filter predicate (Deque snocList consList) = let-  newConsList = StrictList.prependReversed-    (StrictList.filterReversed predicate consList)-    (StrictList.filterReversed predicate snocList)-  in Deque StrictList.Nil newConsList---- |--- /O(n)/.--- Leave only the first elements satisfying the predicate.-takeWhile :: (a -> Bool) -> Deque a -> Deque a-takeWhile predicate (Deque snocList consList) = let-  newConsList = foldr-    (\ a nextState -> if predicate a-      then StrictList.Cons a nextState-      else StrictList.Nil)-    (StrictList.takeWhileFromEnding predicate snocList)-    consList-  in Deque StrictList.Nil newConsList---- |--- /O(n)/.--- Drop the first elements satisfying the predicate.-dropWhile :: (a -> Bool) -> Deque a -> Deque a-dropWhile predicate (Deque snocList consList) = let-  newConsList = StrictList.dropWhile predicate consList-  in case newConsList of-    StrictList.Nil -> Deque StrictList.Nil (StrictList.dropWhileFromEnding predicate snocList)-    _ -> Deque snocList newConsList---- |--- /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 snocList consList) = case consList of-  StrictList.Cons head tail -> Just (head, Deque snocList tail)-  _ -> case StrictList.reverse snocList of-    StrictList.Cons head tail -> Just (head, Deque StrictList.Nil tail)-    _ -> Nothing---- |--- /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 snocList consList) = case snocList of-  StrictList.Cons head tail -> Just (head, Deque tail consList)-  _ -> case StrictList.reverse consList of-    StrictList.Cons head tail -> Just (head, Deque tail StrictList.Nil)-    _ -> Nothing---- |--- /O(1)/. --- Check whether deque is empty.-null :: Deque a -> Bool-null = \ case-  Deque StrictList.Nil StrictList.Nil -> True-  _ -> False---- |--- /O(1)/, occasionally /O(n)/.--- Get the first element if deque is not empty.-head :: Deque a -> Maybe a-head (Deque snocList consList) = case consList of-  StrictList.Cons head _ -> Just head-  _ -> StrictList.last snocList---- |--- /O(1)/, occasionally /O(n)/.--- Get the last element if deque is not empty.-last :: Deque a -> Maybe a-last (Deque snocList consList) = case snocList of-  StrictList.Cons head _ -> Just head-  _ -> StrictList.last consList---- |--- /O(1)/, occasionally /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 snocList consList) = case consList of-  StrictList.Nil -> Deque StrictList.Nil (StrictList.initReversed snocList)-  _ -> Deque snocList (StrictList.tail consList)---- |--- /O(1)/, occasionally /O(n)/.--- Keep all elements but the last one.--- --- 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.initReversed consList) StrictList.Nil-  _ -> Deque (StrictList.tail snocList) consList---instance Eq a => Eq (Deque a) where-  (==) a b = toList a == toList b--instance Show a => Show (Deque a) where-  show = showString "fromList " . show . toList--instance IsList (Deque a) where-  type Item (Deque a) = a-  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-    snocList3 = snocList2-    consList3 = consList1 <> StrictList.prependReversed snocList1 consList2-    in Deque snocList3 consList3--instance Monoid (Deque a) where-  mempty = Deque StrictList.Nil StrictList.Nil-  mappend = (<>)--deriving instance Functor Deque--instance Foldable Deque where-  foldr step init (Deque snocList consList) = foldr step (foldr step init (StrictList.reverse snocList)) consList-  foldl' step init (Deque snocList consList) = foldl' step (foldl' step init consList) (StrictList.reverse snocList)--instance Traversable Deque where-  traverse f (Deque ss cs) =-    (\cs' ss' -> Deque (StrictList.reverse ss') cs') <$> traverse f cs <*> traverse f (StrictList.reverse ss)--instance Applicative Deque where-  pure a = Deque StrictList.Nil (pure a)-  fs <*> as = fromList (toList fs <*> toList as)--instance Monad Deque where-  return = pure-  m >>= f = fromList (toList m >>= toList . f)-  fail = const mempty--instance Alternative Deque where-  empty = mempty-  (<|>) = mappend+import Deque.Prelude+import qualified Deque.Lazy.Defs as LazyDefs+import qualified Deque.Strict.Defs as StrictDefs -instance MonadPlus Deque where-  mzero = empty-  mplus = (<|>)+{-| Convert lazy deque to strict deque. -}+fromLazy :: LazyDefs.Deque a -> StrictDefs.Deque a+fromLazy (LazyDefs.Deque consList snocList) = StrictDefs.Deque (fromList consList) (fromList snocList) -instance MonadFail Deque where-  fail = const mempty+{-| Convert strict deque to lazy deque. -}+toLazy :: StrictDefs.Deque a -> LazyDefs.Deque a+toLazy (StrictDefs.Deque consList snocList) = LazyDefs.Deque (toList consList) (toList snocList)

@@ -0,0 +1,247 @@+{-|+Definitions of strict Deque.++The typical `toList` and `fromList` conversions are provided by means of+the `Foldable` and `IsList` instances.+-}+module Deque.Strict.Defs+where++import Control.Monad (fail)+import Deque.Prelude hiding (tail, init, last, head, null, dropWhile, takeWhile, reverse, filter, take)+import qualified StrictList++-- |+-- Strict double-ended queue (aka Dequeue or Deque) based on head-tail linked list.+data Deque a = Deque !(StrictList.List a) !(StrictList.List a)++-- |+-- /O(n)/.+-- Construct from cons and snoc lists.+fromConsAndSnocLists :: [a] -> [a] -> Deque a+fromConsAndSnocLists consList snocList = Deque (fromList consList) (fromList snocList)++-- |+-- /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)/.+-- Add element in the ending.+snoc :: a -> Deque a -> Deque a+snoc a (Deque consList snocList) = Deque consList (StrictList.Cons a snocList)++-- |+-- /O(1)/.+-- Reverse the deque.+reverse :: Deque a -> Deque a+reverse (Deque consList snocList) = Deque snocList consList++-- |+-- /O(1)/, occasionally /O(n)/.+-- Move the first element to the end.+--+-- @+-- λ toList . shiftLeft $ fromList [1,2,3]+-- [2,3,1]+-- @+shiftLeft :: Deque a -> Deque a+shiftLeft deque = maybe deque (uncurry snoc) (uncons deque)++-- |+-- /O(1)/, occasionally /O(n)/.+-- Move the last element to the beginning.+--+-- @+-- λ toList . shiftRight $ fromList [1,2,3]+-- [3,1,2]+-- @+shiftRight :: Deque a -> Deque a+shiftRight deque = maybe deque (uncurry cons) (unsnoc deque)++-- |+-- /O(n)/.+-- Leave only the elements satisfying the predicate.+filter :: (a -> Bool) -> Deque a -> Deque a+filter predicate (Deque consList snocList) = let+  newConsList = StrictList.prependReversed+    (StrictList.filterReversed predicate consList)+    (StrictList.filterReversed predicate snocList)+  in Deque newConsList StrictList.Nil++-- |+-- /O(n)/.+-- Leave only the specified amount of first elements.+take :: Int -> Deque a -> Deque a+take amount (Deque consList snocList) = let+  newSnocList = let+    buildFromConsList amount !list = if amount > 0+      then \ case+        StrictList.Cons head tail -> buildFromConsList (pred amount) (StrictList.Cons head list) tail+        _ -> buildFromSnocList amount list (StrictList.reverse snocList)+      else const list+    buildFromSnocList amount !list = if amount > 0+      then \ case+        StrictList.Cons head tail -> buildFromSnocList (pred amount) (StrictList.Cons head list) tail+        _ -> list+      else const list+    in buildFromConsList amount StrictList.Nil consList+  in Deque StrictList.Nil newSnocList++-- |+-- /O(n)/.+-- Drop the specified amount of first elements.+drop :: Int -> Deque a -> Deque a+drop amount (Deque consList snocList) = let+  buildFromConsList amount = if amount > 0+    then \ case+      StrictList.Cons _ tail -> buildFromConsList (pred amount) tail+      _ -> buildFromSnocList amount (StrictList.reverse snocList)+    else \ tail -> Deque tail snocList+  buildFromSnocList amount = if amount > 0+    then \ case+      StrictList.Cons _ tail -> buildFromSnocList (pred amount) tail+      _ -> Deque StrictList.Nil StrictList.Nil+    else \ tail -> Deque tail StrictList.Nil+  in buildFromConsList amount consList++-- |+-- /O(n)/.+-- Leave only the first elements satisfying the predicate.+takeWhile :: (a -> Bool) -> Deque a -> Deque a+takeWhile predicate (Deque consList snocList) = let+  newConsList = foldr+    (\ a nextState -> if predicate a+      then StrictList.Cons a nextState+      else StrictList.Nil)+    (StrictList.takeWhileFromEnding predicate snocList)+    consList+  in Deque newConsList StrictList.Nil++-- |+-- /O(n)/.+-- Drop the first elements satisfying the predicate.+dropWhile :: (a -> Bool) -> Deque a -> Deque a+dropWhile predicate (Deque consList snocList) = let+  newConsList = StrictList.dropWhile predicate consList+  in case newConsList of+    StrictList.Nil -> Deque (StrictList.dropWhileFromEnding predicate snocList) StrictList.Nil+    _ -> Deque newConsList snocList++-- |+-- /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+  StrictList.Cons head tail -> Just (head, Deque tail snocList)+  _ -> case StrictList.reverse snocList of+    StrictList.Cons head tail -> Just (head, Deque tail StrictList.Nil)+    _ -> Nothing++-- |+-- /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+  StrictList.Cons head tail -> Just (head, Deque consList tail)+  _ -> case StrictList.reverse consList of+    StrictList.Cons head tail -> Just (head, Deque StrictList.Nil tail)+    _ -> Nothing++-- |+-- /O(1)/. +-- Check whether deque is empty.+null :: Deque a -> Bool+null = \ case+  Deque StrictList.Nil StrictList.Nil -> True+  _ -> False++-- |+-- /O(1)/, occasionally /O(n)/.+-- Get the first element if deque is not empty.+head :: Deque a -> Maybe a+head (Deque consList snocList) = case consList of+  StrictList.Cons head _ -> Just head+  _ -> StrictList.last snocList++-- |+-- /O(1)/, occasionally /O(n)/.+-- Get the last element if deque is not empty.+last :: Deque a -> Maybe a+last (Deque consList snocList) = case snocList of+  StrictList.Cons head _ -> Just head+  _ -> StrictList.last consList++-- |+-- /O(1)/, occasionally /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++-- |+-- /O(1)/, occasionally /O(n)/.+-- Keep all elements but the last one.+-- +-- In case of empty deque returns an empty deque.+init :: Deque a -> Deque a+init (Deque consList snocList) = case snocList of+  StrictList.Nil -> Deque StrictList.Nil (StrictList.initReversed consList)+  _ -> Deque consList (StrictList.tail snocList)+++instance Eq a => Eq (Deque a) where+  (==) a b = toList a == toList b++instance Show a => Show (Deque a) where+  show = show . toList++instance IsList (Deque a) where+  type Item (Deque a) = a+  fromList list = Deque StrictList.Nil (StrictList.fromListReversed list)+  toList (Deque consList snocList) = foldr (:) (toList (StrictList.reverse snocList)) consList++instance Semigroup (Deque a) where+  (<>) (Deque snocList1 consList1) (Deque snocList2 consList2) = let+    consList3 = consList1 <> StrictList.prependReversed snocList1 consList2+    snocList3 = snocList2+    in Deque consList3 snocList3++instance Monoid (Deque a) where+  mempty = Deque StrictList.Nil StrictList.Nil+  mappend = (<>)++deriving instance Functor Deque++instance Foldable Deque where+  foldr step init (Deque consList snocList) = foldr step (foldr step init (StrictList.reverse snocList)) consList+  foldl' step init (Deque consList snocList) = foldl' step (foldl' step init consList) (StrictList.reverse snocList)++instance Traversable Deque where+  traverse f (Deque cs ss) =+    (\cs' ss' -> Deque cs' (StrictList.reverse ss')) <$> traverse f cs <*> traverse f (StrictList.reverse ss)++instance Applicative Deque where+  pure a = Deque (pure a) StrictList.Nil+  fs <*> as = fromList (toList fs <*> toList as)++instance Monad Deque where+  return = pure+  m >>= f = fromList (toList m >>= toList . f)+  fail = const mempty++instance Alternative Deque where+  empty = mempty+  (<|>) = mappend++instance MonadPlus Deque where+  mzero = empty+  mplus = (<|>)++instance MonadFail Deque where+  fail = const mempty

@@ -0,0 +1,162 @@+{-|+Strict Deque API lifted to a Reader monad, \"mtl\"-style.+-}+module Deque.Strict.Reader+where++import Deque.Prelude hiding (tail, init, last, head, null, dropWhile, takeWhile, reverse)+import Deque.Strict (Deque)+import qualified Deque.Strict as Deque+import qualified Deque.Prelude as Prelude+++{-|+/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)/.+Add elements to the begginning.+-}+prepend :: MonadReader (Deque a) m => Deque a -> m (Deque a)+prepend deque = reader (deque <>)++{-|+/O(n)/.+Add elements to the ending.+-}+append :: MonadReader (Deque a) m => Deque a -> m (Deque a)+append deque = reader (<> deque)++{-|+/O(1)/.+Add element in the beginning.+-}+cons :: MonadReader (Deque a) m => a -> m (Deque a)+cons a = reader (Deque.cons a)++{-|+/O(1)/.+Add element in the ending.+-}+snoc :: MonadReader (Deque a) m => a -> m (Deque a)+snoc a = reader (Deque.snoc a)++{-|+/O(1)/.+Reverse the deque.+-}+reverse :: MonadReader (Deque a) m => m (Deque a)+reverse = reader Deque.reverse++{-|+/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)/.+Move the last element to the beginning.+-}+shiftRight :: MonadReader (Deque a) m => m (Deque a)+shiftRight = reader Deque.shiftRight++{-|+/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)/.+Leave only the specified amount of first elements.+-}+take :: MonadReader (Deque a) m => Int -> m (Deque a)+take = reader . Deque.take++{-|+/O(n)/.+Drop the specified amount of first elements.+-}+drop :: MonadReader (Deque a) m => Int -> m (Deque a)+drop = reader . Deque.drop++{-|+/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)/.+Drop the first elements satisfying the predicate.+-}+dropWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a)+dropWhile predicate = reader (Deque.dropWhile predicate)++{-|+/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 = reader (\ 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.+-}+unsnoc :: MonadReader (Deque a) m => m (Maybe a, Deque a)+unsnoc = reader (\ deque -> case Deque.unsnoc deque of+  Nothing -> (Nothing, deque)+  Just (a, newDeque) -> (Just a, newDeque))++{-|+/O(1)/. +Check whether deque is empty.+-}+null :: MonadReader (Deque a) m => m Bool+null = reader Deque.null++{-|+/O(1)/. +Check whether deque is empty.+-}+length :: MonadReader (Deque a) m => m Int+length = reader Prelude.length++{-|+/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)/.+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)/.+Keep all elements but the first one.+-}+tail :: MonadReader (Deque a) m => m (Deque a)+tail = reader Deque.tail++{-|+/O(1)/, occasionally /O(n)/.+Keep all elements but the last one.+-}+init :: MonadReader (Deque a) m => m (Deque a)+init = reader Deque.init

@@ -75,6 +75,20 @@  {-| /O(n)/.+Leave only the specified amount of first elements.+-}+take :: MonadState (Deque a) m => Int -> m ()+take = modify . Deque.take++{-|+/O(n)/.+Drop the specified amount of first elements.+-}+drop :: MonadState (Deque a) m => Int -> m ()+drop = modify . Deque.drop++{-|+/O(n)/. Leave only the first elements satisfying the predicate. -} takeWhile :: MonadState (Deque a) m => (a -> Bool) -> m ()@@ -136,17 +150,13 @@ {-| /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+tail :: MonadState (Deque a) m => m ()+tail = modify Deque.tail  {-| /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+init :: MonadState (Deque a) m => m ()+init = modify Deque.init

@@ -1,6 +1,6 @@ module Main where -import Prelude hiding (toList)+import Prelude hiding (toList, choose) import GHC.Exts as Exports (IsList(..)) import Test.QuickCheck.Instances import Test.Tasty@@ -21,14 +21,35 @@     testImplementation "Strict"       toList fromList Strict.fromConsAndSnocLists       Strict.cons Strict.snoc Strict.reverse-      Strict.shiftLeft Strict.shiftRight Strict.filter Strict.takeWhile Strict.dropWhile+      Strict.shiftLeft Strict.shiftRight Strict.filter Strict.take Strict.drop Strict.takeWhile Strict.dropWhile       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.takeWhile Lazy.dropWhile+      Lazy.shiftLeft Lazy.shiftRight Lazy.filter Lazy.take Lazy.drop Lazy.takeWhile Lazy.dropWhile       Lazy.uncons Lazy.unsnoc Lazy.null Lazy.head Lazy.last Lazy.tail Lazy.init+    ,+    testGroup "Conversions" $+    [+      testGroup "Strict" $+      [+        testProperty "toLazy" $ forAll strictAndLazyDequeGen $ \ (strictDeque, lazyDeque) ->+        Strict.toLazy strictDeque === lazyDeque+        ,+        testProperty "fromLazy" $ forAll strictAndLazyDequeGen $ \ (strictDeque, lazyDeque) ->+        Strict.fromLazy lazyDeque === strictDeque+      ]+      ,+      testGroup "Lazy" $+      [+        testProperty "toStrict" $ forAll strictAndLazyDequeGen $ \ (strictDeque, lazyDeque) ->+        Lazy.toStrict lazyDeque === strictDeque+        ,+        testProperty "fromStrict" $ forAll strictAndLazyDequeGen $ \ (strictDeque, lazyDeque) ->+        Lazy.fromStrict strictDeque === lazyDeque+      ]+    ]   ]  {-|@@ -37,7 +58,7 @@ testImplementation name   (toList :: forall a. f a -> [a]) fromList fromConsAndSnocLists   cons snoc reverse-  shiftLeft shiftRight filter takeWhile dropWhile+  shiftLeft shiftRight filter take drop takeWhile dropWhile   uncons unsnoc null head last tail init =     testGroup ("Deque implementation: " <> name) $     [@@ -51,7 +72,7 @@       deque === fromList list       ,       testProperty "show" $ forAll dequeAndListGen $ \ (deque, list) ->-      show deque === "fromList " <> show list+      show deque === show list       ,       testProperty "cons" $ forAll ((,) <$> arbitrary <*> dequeAndListGen) $ \ (a, (deque, list)) ->       toList (cons a deque) === a : list@@ -73,6 +94,12 @@       testProperty "filter" $ forAll ((,) <$> predicateGen <*> dequeAndListGen) $ \ (predicate, (deque, list)) ->       toList (filter predicate deque) === List.filter predicate list       ,+      testProperty "take" $ forAll ((,) <$> arbitrary <*> dequeAndListGen) $ \ (amount, (deque, list)) ->+      toList (take amount deque) === List.take amount list+      ,+      testProperty "drop" $ forAll ((,) <$> arbitrary <*> dequeAndListGen) $ \ (amount, (deque, list)) ->+      toList (drop amount deque) === List.drop amount list+      ,       testProperty "takeWhile" $ forAll ((,) <$> predicateGen <*> dequeAndListGen) $ \ (predicate, (deque, list)) ->       toList (takeWhile predicate deque) === List.takeWhile predicate list       ,@@ -118,21 +145,44 @@       ,       testProperty "foldr" $ forAll dequeAndListGen $ \ (deque, list) ->       foldr (:) [] deque === foldr (:) [] list+      ,+      testProperty "traverse" $ forAll dequeAndListGen $ \ (deque, list) -> let+        fn x = if mod x 2 == 0 then Right x else Left x+        in fmap toList (traverse fn deque) === traverse fn list     ]     where-      listGen = arbitrary @[Word8]       dequeAndListGen = do         consList <- listGen         snocList <- listGen         return (fromConsAndSnocLists consList snocList, consList <> List.reverse snocList)-      predicateGen = do-        op <- elements [(>), (>=), (==), (<=), (<)]-        x <- arbitrary @Word8-        return (op x)+      kleisliGen :: Gen (Word8 -> [Word8])+      kleisliGen = do+        list <- listGen+        return $ \ x -> fmap (+ x) list -{-|-A workaround to satisfy QuickCheck's requirements,-when we need to generate a predicate.--}+sizedListGen maxSize = do+  length <- choose (0, maxSize)+  replicateM length (arbitrary @Word8)++listGen = arbitrary @[Word8]++predicateGen = do+  op <- elements [(>), (>=), (==), (<=), (<)]+  x <- arbitrary @Word8+  return (op x)++strictAndLazyDequeGen = do+  consList <- listGen+  snocList <- listGen+  return (Strict.fromConsAndSnocLists consList snocList, Lazy.fromConsAndSnocLists consList snocList)+++-- * Workarounds to satisfy QuickCheck's requirements,+-- when we need to generate a predicate.+-------------------------+ instance Show (Word8 -> Bool) where   show _ = "(Word8 -> Bool) function"++instance Show (Word8 -> [Word8]) where+  show _ = "(Word8 -> [Word8]) function"