deque 0.2.7 → 0.3

raw patch · 9 files changed

+1052/−244 lines, 9 filesdep +mtlPVP ok

version bump matches the API change (PVP)

Dependencies added: mtl

API changes (from Hackage documentation)

Files

• deque.cabal +15/−8
• library/Deque.hs +0/−216
• library/Deque/Lazy.hs +226/−0
• library/Deque/Lazy/State.hs +115/−0
• library/Deque/Prelude.hs +78/−0
• library/Deque/Strict.hs +230/−0
• library/Deque/Strict/State.hs +115/−0
• library/Deque/StrictList.hs +155/−0
• test/Main.hs +118/−20

@@ -1,9 +1,9 @@ name: deque-version: 0.2.7-synopsis: Double-ended queue+version: 0.3+synopsis: Double-ended queues description:-  An implementation of Double-Ended Queue (aka Dequeue or Deque)-  based on the head-tail linked list.+  Strict and lazy implementations of Double-Ended Queue (aka Dequeue or Deque)+  based on head-tail linked list. homepage: https://github.com/nikita-volkov/deque bug-reports: https://github.com/nikita-volkov/deque/issues author: Nikita Volkov <nikita.y.volkov@mail.ru>@@ -20,17 +20,24 @@  library   hs-source-dirs: library-  default-extensions: DeriveFunctor, ScopedTypeVariables, StandaloneDeriving+  default-extensions: BangPatterns, DeriveDataTypeable, DeriveGeneric, DeriveFunctor, DeriveTraversable, FlexibleContexts, FlexibleInstances, LambdaCase, NoImplicitPrelude, RankNTypes, ScopedTypeVariables, StandaloneDeriving, TypeApplications, TypeFamilies   default-language: Haskell2010   exposed-modules:-    Deque+    Deque.Lazy+    Deque.Lazy.State+    Deque.Strict+    Deque.Strict.State+  other-modules:+    Deque.Prelude+    Deque.StrictList   build-depends:-    base >= 4.9 && < 5+    base >=4.9 && <5,+    mtl >=2.2 && <3  test-suite test   type: exitcode-stdio-1.0   hs-source-dirs: test-  default-extensions: DeriveFunctor, ScopedTypeVariables, StandaloneDeriving+  default-extensions: BangPatterns, DeriveDataTypeable, DeriveGeneric, DeriveFunctor, DeriveTraversable, FlexibleContexts, FlexibleInstances, LambdaCase, NoImplicitPrelude, RankNTypes, ScopedTypeVariables, StandaloneDeriving, TypeApplications, TypeFamilies   default-language: Haskell2010   main-is:     Main.hs

@@ -1,216 +0,0 @@-module Deque where--import Prelude hiding (foldr, foldr', foldl')-import Control.Applicative-import Control.Monad-import Control.Monad.Fail-import Data.Foldable-import Data.Traversable-import Data.Maybe-import Data.Monoid hiding ((<>))-import Data.Semigroup-import qualified Data.List as List---- |--- Double-ended queue (aka Dequeue or Deque) based on the head-tail linked list.--- Can be cycled. See `shiftLeft` and `shiftRight`.-data Deque a =-  Deque [a] [a]---- |--- /O(1)/.--- `toList` is available from the `Foldable` instance.-fromList :: [a] -> Deque a-fromList =-  Deque []---- |--- /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)/.------ @--- λ 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)/.------ @--- λ toList . shiftRight $ fromList [1,2,3]--- [3,1,2]--- @-shiftRight :: Deque a -> Deque a-shiftRight deque =-  maybe deque (uncurry cons) (unsnoc deque)---- |--- /O(1)/.--- Prepend an element.-cons :: a -> Deque a -> Deque a-cons a (Deque snocList consList) =-  Deque snocList (a : consList)---- |--- /O(1)/.--- Append an element.-snoc :: a -> Deque a -> Deque a-snoc a (Deque snocList consList) =-  Deque (a : snocList) consList---- |--- /O(1)/, occasionally /O(n)/.-uncons :: Deque a -> Maybe (a, Deque a)-uncons (Deque snocList consList) =-  case consList of-    head : tail ->-      Just (head, Deque snocList tail)-    _ ->-      case Prelude.reverse snocList of-        head : tail ->-          Just (head, Deque [] tail)-        _ ->-          Nothing---- |--- /O(1)/, occasionally /O(n)/.-unsnoc :: Deque a -> Maybe (a, Deque a)-unsnoc (Deque snocList consList) =-  case snocList of-    head : tail ->-      Just (head, Deque tail consList)-    _ ->-      case Prelude.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 :: Deque a -> Deque a-reverse (Deque snocList consList) =-  Deque consList snocList---- |--- /O(1)/. -null :: Deque a -> Bool-null (Deque snocList consList) =-  List.null snocList && List.null consList---- |--- /O(1)/, occasionally /O(n)/.-head :: Deque a -> Maybe a-head =-  fmap fst . uncons---- |--- /O(1)/, occasionally /O(n)/.-tail :: Deque a -> Deque a-tail =-  fromMaybe <$> id <*> fmap snd . uncons---- |--- /O(1)/, occasionally /O(n)/.-init :: Deque a -> Deque a-init =-  fromMaybe <$> id <*> fmap snd . unsnoc---- |--- /O(1)/, occasionally /O(n)/.-last :: Deque a -> Maybe a-last =-  fmap fst . unsnoc---deriving instance Eq a => Eq (Deque a)--deriving instance Show a => Show (Deque a)--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 (Prelude.reverse ss') cs') <$> traverse f cs <*> traverse f (Prelude.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

@@ -0,0 +1,226 @@+{-|+Definitions of lazy Deque.++The typical `toList` and `fromList` conversions are provided by means of+the `Foldable` and `IsList` instances.+-}+module Deque.Lazy+(+  Deque,+  fromConsAndSnocLists,+  cons,+  snoc,+  reverse,+  shiftLeft,+  shiftRight,+  filter,+  takeWhile,+  dropWhile,+  uncons,+  unsnoc,+  null,+  head,+  last,+  tail,+  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)/.+-- Revert 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 = (<|>)++instance MonadFail Deque where+  fail = const mempty++-- |+-- /O(1)/.+instance IsList (Deque a) where+  type Item (Deque a) = a+  fromList = Deque []+  toList (Deque snocList consList) = consList <> List.reverse snocList+  

@@ -0,0 +1,115 @@+{-|+Lazy Deque API lifted to a State monad, \"mtl\"-style.+-}+module Deque.Lazy.State+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(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.+snoc :: MonadState (Deque a) m => a -> m ()+snoc a = modify (Deque.snoc a)++-- |+-- /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.+shiftLeft :: MonadState (Deque a) m => m ()+shiftLeft = modify Deque.shiftLeft++-- |+-- /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.+filter :: MonadState (Deque a) m => (a -> Bool) -> m ()+filter predicate = modify (Deque.filter 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.+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.+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.+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.+null :: MonadState (Deque a) m => m Bool+null = gets Deque.null++-- |+-- /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.+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.+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.+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.+init :: MonadState (Deque a) m => m (Deque a)+init = gets Deque.init

@@ -0,0 +1,78 @@+module Deque.Prelude+(+  module Exports,+)+where+++-- base+-------------------------+import Control.Applicative as Exports+import Control.Arrow as Exports+import Control.Category as Exports+import Control.Concurrent as Exports+import Control.Exception as Exports+import Control.Monad as Exports hiding (fail, mapM_, sequence_, forM_, msum, mapM, sequence, forM)+import Control.Monad.IO.Class as Exports+import Control.Monad.Fail as Exports+import Control.Monad.Fix as Exports hiding (fix)+import Control.Monad.ST as Exports+import Data.Bits as Exports+import Data.Bool as Exports+import Data.Char as Exports+import Data.Coerce as Exports+import Data.Complex as Exports+import Data.Data as Exports+import Data.Dynamic as Exports+import Data.Either as Exports+import Data.Fixed as Exports+import Data.Foldable as Exports hiding (toList)+import Data.Function as Exports hiding (id, (.))+import Data.Functor as Exports+import Data.Functor.Identity as Exports+import Data.Int as Exports+import Data.IORef as Exports+import Data.Ix as Exports+import Data.List as Exports hiding (sortOn, isSubsequenceOf, uncons, concat, foldr, foldl1, maximum, minimum, product, sum, all, and, any, concatMap, elem, foldl, foldr1, notElem, or, find, maximumBy, minimumBy, mapAccumL, mapAccumR, foldl')+import Data.Maybe as Exports+import Data.Monoid as Exports hiding (Last(..), First(..), (<>))+import Data.Ord as Exports+import Data.Proxy as Exports+import Data.Ratio as Exports+import Data.Semigroup as Exports+import Data.STRef as Exports+import Data.String as Exports+import Data.Traversable as Exports+import Data.Tuple as Exports+import Data.Unique as Exports+import Data.Version as Exports+import Data.Word as Exports+import Debug.Trace as Exports+import Foreign.ForeignPtr as Exports+import Foreign.Ptr as Exports+import Foreign.StablePtr as Exports+import Foreign.Storable as Exports hiding (sizeOf, alignment)+import GHC.Conc as Exports hiding (withMVar, threadWaitWriteSTM, threadWaitWrite, threadWaitReadSTM, threadWaitRead)+import GHC.Exts as Exports (lazy, inline, sortWith, groupWith, IsList(..))+import GHC.Generics as Exports (Generic, Generic1)+import GHC.IO.Exception as Exports+import Numeric as Exports+import Prelude as Exports hiding (fail, concat, foldr, mapM_, sequence_, foldl1, maximum, minimum, product, sum, all, and, any, concatMap, elem, foldl, foldr1, notElem, or, mapM, sequence, id, (.))+import System.Environment as Exports+import System.Exit as Exports+import System.IO as Exports+import System.IO.Error as Exports+import System.IO.Unsafe as Exports+import System.Mem as Exports+import System.Mem.StableName as Exports+import System.Timeout as Exports+import Text.ParserCombinators.ReadP as Exports (ReadP, ReadS, readP_to_S, readS_to_P)+import Text.ParserCombinators.ReadPrec as Exports (ReadPrec, readPrec_to_P, readP_to_Prec, readPrec_to_S, readS_to_Prec)+import Text.Printf as Exports (printf, hPrintf)+import Text.Read as Exports (Read(..), readMaybe, readEither)+import Unsafe.Coerce as Exports++-- mtl+-------------------------+import Control.Monad.State.Strict as Exports hiding (fail)+

@@ -0,0 +1,230 @@+{-|+Definitions of strict Deque.++The typical `toList` and `fromList` conversions are provided by means of+the `Foldable` and `IsList` instances.+-}+module Deque.Strict+(+  Deque,+  fromConsAndSnocLists,+  cons,+  snoc,+  reverse,+  shiftLeft,+  shiftRight,+  filter,+  takeWhile,+  dropWhile,+  uncons,+  unsnoc,+  null,+  head,+  last,+  tail,+  init,+)+where++import Control.Monad (fail)+import Deque.Prelude hiding (tail, init, last, head, null, dropWhile, takeWhile, reverse, filter)+import qualified Deque.StrictList as 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)/.+-- 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)/.+-- Revert 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.filterReverse predicate consList)+    (StrictList.filterReverse 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.reverseInit 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.reverseInit 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.fromReverseList list) StrictList.Nil+  toList (Deque snocList consList) = foldr (:) (StrictList.toReverseList 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 consList) (StrictList.reverse snocList)+  foldl' step init (Deque snocList consList) = foldl' step (foldl' step init consList) (StrictList.reverse consList)++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++instance MonadPlus Deque where+  mzero = empty+  mplus = (<|>)++instance MonadFail Deque where+  fail = const mempty

@@ -0,0 +1,115 @@+{-|+Strict Deque API lifted to a State monad, \"mtl\"-style.+-}+module Deque.Strict.State+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(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.+snoc :: MonadState (Deque a) m => a -> m ()+snoc a = modify (Deque.snoc a)++-- |+-- /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.+shiftLeft :: MonadState (Deque a) m => m ()+shiftLeft = modify Deque.shiftLeft++-- |+-- /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.+filter :: MonadState (Deque a) m => (a -> Bool) -> m ()+filter predicate = modify (Deque.filter 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.+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.+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.+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.+null :: MonadState (Deque a) m => m Bool+null = gets Deque.null++-- |+-- /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.+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.+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.+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.+init :: MonadState (Deque a) m => m (Deque a)+init = gets Deque.init

@@ -0,0 +1,155 @@+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 []

@@ -1,6 +1,7 @@ module Main where -import Prelude+import Prelude hiding (toList)+import GHC.Exts as Exports (IsList(..)) import Test.QuickCheck.Instances import Test.Tasty import Test.Tasty.Runners@@ -8,27 +9,124 @@ import Test.Tasty.QuickCheck import qualified Test.QuickCheck as QuickCheck import qualified Test.QuickCheck.Property as QuickCheck-import qualified Deque as Deque import qualified Data.List as List+import qualified Deque.Lazy as Lazy+import qualified Deque.Strict as Strict   main =   defaultMain $-  testGroup "List roundtrips" $ let-  testPredicateProperty name listOp dequeOp =-    testProperty name $ \ (list1 :: [Int], list2 :: [Int], threshold :: Int, direction :: Int) -> let-      compare = case mod direction 5 of-        0 -> (>)-        1 -> (>=)-        2 -> (==)-        3 -> (<=)-        4 -> (<)-      predicate = compare threshold-      in-        listOp predicate (list1 <> list2) ===-        toList (dequeOp predicate (Deque.Deque (reverse list2) list1))-    in [-        testPredicateProperty "takeWhile" List.takeWhile Deque.takeWhile-        ,-        testPredicateProperty "dropWhile" List.dropWhile Deque.dropWhile-      ]+  testGroup "" $+  [+    testImplementation "Strict"+      toList fromList Strict.fromConsAndSnocLists+      Strict.cons Strict.snoc Strict.reverse+      Strict.shiftLeft Strict.shiftRight Strict.filter 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.uncons Lazy.unsnoc Lazy.null Lazy.head Lazy.last Lazy.tail Lazy.init+  ]++{-|+Test group, which abstracts over the implementation of deque.+-}+testImplementation name+  (toList :: forall a. f a -> [a]) fromList fromConsAndSnocLists+  cons snoc reverse+  shiftLeft shiftRight filter takeWhile dropWhile+  uncons unsnoc null head last tail init =+    testGroup ("Deque implementation: " <> name) $+    [+      testProperty "toList" $ forAll dequeAndListGen $ \ (deque, list) ->+      toList deque === list+      ,+      testProperty "fromList" $ forAll listGen $ \ list ->+      toList (fromList list) === list+      ,+      testProperty "eq" $ forAll dequeAndListGen $ \ (deque, list) ->+      deque === fromList list+      ,+      testProperty "show" $ forAll dequeAndListGen $ \ (deque, list) ->+      show deque === "fromList " <> show list+      ,+      testProperty "cons" $ forAll ((,) <$> arbitrary <*> dequeAndListGen) $ \ (a, (deque, list)) ->+      toList (cons a deque) === a : list+      ,+      testProperty "snoc" $ forAll ((,) <$> arbitrary <*> dequeAndListGen) $ \ (a, (deque, list)) ->+      toList (snoc a deque) === list <> [a]+      ,+      testProperty "reverse" $ forAll dequeAndListGen $ \ (deque, list) ->+      toList (reverse deque) === List.reverse list+      ,+      testProperty "shiftLeft" $ forAll dequeAndListGen $ \ (deque, list) ->+      toList (shiftLeft deque) === List.drop 1 list <> List.take 1 list+      ,+      testProperty "shiftRight" $ forAll dequeAndListGen $ \ (deque, list) ->+      toList (shiftRight deque) === case list of+        [] -> []+        _ -> List.last list : List.init list+      ,+      testProperty "filter" $ forAll ((,) <$> predicateGen <*> dequeAndListGen) $ \ (predicate, (deque, list)) ->+      toList (filter predicate deque) === List.filter predicate list+      ,+      testProperty "takeWhile" $ forAll ((,) <$> predicateGen <*> dequeAndListGen) $ \ (predicate, (deque, list)) ->+      toList (takeWhile predicate deque) === List.takeWhile predicate list+      ,+      testProperty "dropWhile" $ forAll ((,) <$> predicateGen <*> dequeAndListGen) $ \ (predicate, (deque, list)) ->+      toList (dropWhile predicate deque) === List.dropWhile predicate list+      ,+      testProperty "uncons" $ forAll dequeAndListGen $ \ (deque, list) ->+      fmap (fmap toList) (uncons deque) === List.uncons list+      ,+      testProperty "unsnoc" $ forAll dequeAndListGen $ \ (deque, list) ->+      fmap (fmap toList) (unsnoc deque) === case list of+        [] -> Nothing+        _ -> Just (List.last list, List.init list)+      ,+      testProperty "null" $ forAll dequeAndListGen $ \ (deque, list) ->+      null deque === List.null list+      ,+      testProperty "head" $ forAll dequeAndListGen $ \ (deque, list) ->+      head deque === case list of+        head : _ -> Just head+        _ -> Nothing+      ,+      testProperty "last" $ forAll dequeAndListGen $ \ (deque, list) ->+      last deque === case list of+        [] -> Nothing+        _ -> Just (List.last list)+      ,+      testProperty "tail" $ forAll dequeAndListGen $ \ (deque, list) ->+      toList (tail deque) === case list of+        _ : tail -> tail+        _ -> []+      ,+      testProperty "init" $ forAll dequeAndListGen $ \ (deque, list) ->+      toList (init deque) === case list of+        [] -> []+        _ -> List.init list+      ,+      testProperty "ap" $ forAll ((,) <$> dequeAndListGen <*> dequeAndListGen) $ \ ((deque1, list1), (deque2, list2)) ->+      toList ((,) <$> deque1 <*> deque2) === ((,) <$> list1 <*> list2)+    ]+    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)++{-|+A workaround to satisfy QuickCheck's requirements,+when we need to generate a predicate.+-}+instance Show (Word8 -> Bool) where+  show _ = "(Word8 -> Bool) function"