deque 0.4.4 → 0.4.4.1
raw patch · 12 files changed
+943/−970 lines, 12 filesdep −QuickCheckdep −quickcheck-instancesdep −tasty-hunitdep ~deepseqsetup-changedPVP ok
version bump matches the API change (PVP)
Dependencies removed: QuickCheck, quickcheck-instances, tasty-hunit
Dependency ranges changed: deepseq
API changes (from Hackage documentation)
Files
- Setup.hs +0/−2
- deque.cabal +65/−35
- library/Deque/Lazy.hs +31/−33
- library/Deque/Lazy/Defs.hs +90/−84
- library/Deque/Lazy/Reader.hs +104/−123
- library/Deque/Lazy/State.hs +106/−125
- library/Deque/Prelude.hs +22/−37
- library/Deque/Strict.hs +31/−33
- library/Deque/Strict/Defs.hs +114/−90
- library/Deque/Strict/Reader.hs +105/−124
- library/Deque/Strict/State.hs +107/−126
- test/Main.hs +168/−158
− Setup.hs
@@ -1,2 +0,0 @@-import Distribution.Simple-main = defaultMain
deque.cabal view
@@ -1,28 +1,44 @@-name: deque-version: 0.4.4-synopsis: Double-ended queues+cabal-version: 3.0+name: deque+version: 0.4.4.1+synopsis: Double-ended queues description: 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>-maintainer: Nikita Volkov <nikita.y.volkov@mail.ru>-copyright: (c) 2016, Nikita Volkov-license: MIT-license-file: LICENSE-build-type: Simple-cabal-version: >=1.10 +category: Data+homepage: https://github.com/nikita-volkov/deque+bug-reports: https://github.com/nikita-volkov/deque/issues+author: Nikita Volkov <nikita.y.volkov@mail.ru>+maintainer: Nikita Volkov <nikita.y.volkov@mail.ru>+copyright: (c) 2016, Nikita Volkov+license: MIT+license-file: LICENSE+ source-repository head- type: git+ type: git location: git://github.com/nikita-volkov/deque.git 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+ hs-source-dirs: library+ default-extensions:+ NoImplicitPrelude+ BangPatterns+ DeriveDataTypeable+ DeriveFunctor+ DeriveGeneric+ DeriveTraversable+ FlexibleContexts+ FlexibleInstances+ LambdaCase+ RankNTypes+ ScopedTypeVariables+ StandaloneDeriving+ TypeApplications+ TypeFamilies++ ghc-options: -funbox-strict-fields+ default-language: Haskell2010 exposed-modules: Deque.Lazy Deque.Lazy.Reader@@ -30,28 +46,42 @@ Deque.Strict Deque.Strict.Reader Deque.Strict.State+ other-modules: Deque.Lazy.Defs- Deque.Strict.Defs Deque.Prelude+ Deque.Strict.Defs+ build-depends:- base >=4.9 && <5,- deepseq >=1.4.3 && <1.5,- hashable >=1.2 && <2,- mtl >=2.2 && <3,- strict-list >=0.1.6 && <0.2+ , base >=4.9 && <5+ , deepseq >=1.4.3 && <2+ , hashable >=1.2 && <2+ , mtl >=2.2 && <3+ , strict-list >=0.1.6 && <0.2 test-suite test- type: exitcode-stdio-1.0- hs-source-dirs: test- default-extensions: BangPatterns, DeriveDataTypeable, DeriveGeneric, DeriveFunctor, DeriveTraversable, FlexibleContexts, FlexibleInstances, LambdaCase, NoImplicitPrelude, RankNTypes, ScopedTypeVariables, StandaloneDeriving, TypeApplications, TypeFamilies- default-language: Haskell2010- main-is: Main.hs+ type: exitcode-stdio-1.0+ hs-source-dirs: test+ default-extensions:+ NoImplicitPrelude+ BangPatterns+ DeriveDataTypeable+ DeriveFunctor+ DeriveGeneric+ DeriveTraversable+ FlexibleContexts+ FlexibleInstances+ LambdaCase+ RankNTypes+ ScopedTypeVariables+ StandaloneDeriving+ TypeApplications+ TypeFamilies++ default-language: Haskell2010+ main-is: Main.hs build-depends:- deque,- QuickCheck >=2.8.1 && <3,- quickcheck-instances >=0.3.11 && <0.4,- rerebase <2,- tasty >=0.12 && <2,- tasty-hunit >=0.9 && <0.11,- tasty-quickcheck >=0.9 && <0.11+ , deque+ , rerebase <2+ , tasty >=0.12 && <2+ , tasty-quickcheck >=0.9 && <0.11
library/Deque/Lazy.hs view
@@ -1,44 +1,42 @@-{-|-Definitions of lazy Deque.--The typical `toList` and `fromList` conversions are provided by means of-the `Foldable` and `IsList` instances.--}+-- |+-- Definitions of lazy Deque.+--+-- The typical `toList` and `fromList` conversions are provided by means of+-- the `Foldable` and `IsList` instances. module Deque.Lazy-(- 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.span,- LazyDefs.uncons,- LazyDefs.unsnoc,- LazyDefs.null,- LazyDefs.head,- LazyDefs.last,- LazyDefs.tail,- LazyDefs.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.span,+ LazyDefs.uncons,+ LazyDefs.unsnoc,+ LazyDefs.null,+ LazyDefs.head,+ LazyDefs.last,+ LazyDefs.tail,+ LazyDefs.init,+ ) where -import Deque.Prelude import qualified Deque.Lazy.Defs as LazyDefs+import Deque.Prelude import qualified Deque.Strict.Defs as StrictDefs -{-| Convert strict deque to lazy deque. -}+-- | Convert strict deque to lazy deque. fromStrict :: StrictDefs.Deque a -> LazyDefs.Deque a fromStrict (StrictDefs.Deque consList snocList) = LazyDefs.Deque (toList consList) (toList snocList) -{-| Convert lazy deque to strict deque. -}+-- | Convert lazy deque to strict deque. toStrict :: LazyDefs.Deque a -> StrictDefs.Deque a toStrict (LazyDefs.Deque consList snocList) = StrictDefs.Deque (fromList consList) (fromList snocList)
library/Deque/Lazy/Defs.hs view
@@ -1,17 +1,14 @@ {-# LANGUAGE CPP #-}-{-|-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+-- |+-- 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+import Deque.Prelude hiding (dropWhile, filter, head, init, last, null, reverse, tail, take, takeWhile) -- | -- Lazy double-ended queue (aka Dequeue or Deque) based on head-tail linked list.@@ -33,76 +30,84 @@ -- \(\mathcal{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 []+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 [] -- | -- \(\mathcal{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+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 -- | -- \(\mathcal{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 []+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 [] -- | -- \(\mathcal{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+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 -- | -- \(\mathcal{O}(n)\). -- Perform `takeWhile` and `dropWhile` in a single operation. span :: (a -> Bool) -> Deque a -> (Deque a, Deque a) span predicate (Deque consList snocList) = case List.span predicate consList of- (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)+ (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) -- | -- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).@@ -161,10 +166,10 @@ -- | -- \(\mathcal{O}(n)\). prepend :: Deque a -> Deque a -> Deque a-prepend (Deque consList1 snocList1) (Deque consList2 snocList2) = let- consList = consList1- snocList = snocList2 ++ foldl' (flip (:)) snocList1 consList2- in Deque consList snocList+prepend (Deque consList1 snocList1) (Deque consList2 snocList2) =+ let consList = consList1+ snocList = snocList2 ++ foldl' (flip (:)) snocList1 consList2+ in Deque consList snocList -- | -- \(\mathcal{O}(1)\).@@ -173,7 +178,7 @@ reverse (Deque consList snocList) = Deque snocList consList -- |--- \(\mathcal{O}(1)\). +-- \(\mathcal{O}(1)\). -- Check whether deque is empty. null :: Deque a -> Bool null (Deque consList snocList) = List.null snocList && List.null consList@@ -187,7 +192,7 @@ -- | -- \(\mathcal{O}(1)\), occasionally \(\mathcal{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@@ -195,7 +200,7 @@ -- | -- \(\mathcal{O}(1)\), occasionally \(\mathcal{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@@ -206,11 +211,10 @@ last :: Deque a -> Maybe a last = fmap fst . unsnoc --instance Eq a => Eq (Deque a) where+instance (Eq a) => Eq (Deque a) where (==) a b = toList a == toList b -instance Show a => Show (Deque a) where+instance (Show a) => Show (Deque a) where show = show . toList instance Semigroup (Deque a) where@@ -234,22 +238,22 @@ instance Applicative Deque where pure a = Deque [] [a]- (<*>) (Deque fnConsList fnSnocList) (Deque argConsList argSnocList) = let- consList = let- fnStep fn resultConsList = let- argStep arg = (:) (fn arg)- in foldr argStep (foldr argStep resultConsList (List.reverse argSnocList)) argConsList- in foldr fnStep (foldr fnStep [] (List.reverse fnSnocList)) fnConsList - in Deque consList []+ (<*>) (Deque fnConsList fnSnocList) (Deque argConsList argSnocList) =+ let consList =+ let fnStep fn resultConsList =+ let argStep arg = (:) (fn arg)+ in foldr argStep (foldr argStep resultConsList (List.reverse argSnocList)) argConsList+ in foldr fnStep (foldr fnStep [] (List.reverse fnSnocList)) fnConsList+ in Deque consList [] instance Monad Deque where return = pure- (>>=) (Deque aConsList aSnocList) k = let- consList = let- aStep a accBConsList = case k a of- Deque bConsList bSnocList -> bConsList <> foldl' (flip (:)) accBConsList bSnocList- in foldr aStep (foldr aStep [] (List.reverse aSnocList)) aConsList- in Deque consList []+ (>>=) (Deque aConsList aSnocList) k =+ let consList =+ let aStep a accBConsList = case k a of+ Deque bConsList bSnocList -> bConsList <> foldl' (flip (:)) accBConsList bSnocList+ in foldr aStep (foldr aStep [] (List.reverse aSnocList)) aConsList+ in Deque consList [] #if !(MIN_VERSION_base(4,13,0)) fail = const mempty #endif@@ -273,9 +277,11 @@ toList (Deque consList snocList) = consList <> List.reverse snocList deriving instance Generic (Deque a)+ deriving instance Generic1 Deque -instance Hashable a => Hashable (Deque a)+instance (Hashable a) => Hashable (Deque a) -instance NFData a => NFData (Deque a)+instance (NFData a) => NFData (Deque a)+ instance NFData1 Deque
library/Deque/Lazy/Reader.hs view
@@ -1,169 +1,150 @@-{-|-Lazy Deque API lifted to a Reader monad, \"mtl\"-style.--}-module Deque.Lazy.Reader-where+-- |+-- 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 Deque.Prelude hiding (dropWhile, head, init, last, null, reverse, tail, takeWhile) import qualified Deque.Prelude as Prelude --{-|-\(\mathcal{O}(n)\).-Modify each element of the queue.--}-map :: MonadReader (Deque a) m => (a -> b) -> m (Deque b)+-- |+-- \(\mathcal{O}(n)\).+-- Modify each element of the queue.+map :: (MonadReader (Deque a) m) => (a -> b) -> m (Deque b) map f = reader (fmap f) -{-|-\(\mathcal{O}(n)\).-Add elements to the begginning.--}-prepend :: MonadReader (Deque a) m => Deque a -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Add elements to the begginning.+prepend :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) prepend deque = reader (deque <>) -{-|-\(\mathcal{O}(n)\).-Add elements to the ending.--}-append :: MonadReader (Deque a) m => Deque a -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Add elements to the ending.+append :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) append deque = reader (<> deque) -{-|-\(\mathcal{O}(1)\).-Add element in the beginning.--}-cons :: MonadReader (Deque a) m => a -> m (Deque a)+-- |+-- \(\mathcal{O}(1)\).+-- Add element in the beginning.+cons :: (MonadReader (Deque a) m) => a -> m (Deque a) cons a = reader (Deque.cons a) -{-|-\(\mathcal{O}(1)\).-Add element in the ending.--}-snoc :: MonadReader (Deque a) m => a -> m (Deque a)+-- |+-- \(\mathcal{O}(1)\).+-- Add element in the ending.+snoc :: (MonadReader (Deque a) m) => a -> m (Deque a) snoc a = reader (Deque.snoc a) -{-|-\(\mathcal{O}(1)\).-Reverse the deque.--}-reverse :: MonadReader (Deque a) m => m (Deque a)+-- |+-- \(\mathcal{O}(1)\).+-- Reverse the deque.+reverse :: (MonadReader (Deque a) m) => m (Deque a) reverse = reader Deque.reverse -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Move the first element to the end.--}-shiftLeft :: MonadReader (Deque a) m => m (Deque a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Move the first element to the end.+shiftLeft :: (MonadReader (Deque a) m) => m (Deque a) shiftLeft = reader Deque.shiftLeft -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Move the last element to the beginning.--}-shiftRight :: MonadReader (Deque a) m => m (Deque a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Move the last element to the beginning.+shiftRight :: (MonadReader (Deque a) m) => m (Deque a) shiftRight = reader Deque.shiftRight -{-|-\(\mathcal{O}(n)\).-Leave only the elements satisfying the predicate.--}-filter :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the elements satisfying the predicate.+filter :: (MonadReader (Deque a) m) => (a -> Bool) -> m (Deque a) filter predicate = reader (Deque.filter predicate) -{-|-\(\mathcal{O}(n)\).-Leave only the specified amount of first elements.--}-take :: MonadReader (Deque a) m => Int -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the specified amount of first elements.+take :: (MonadReader (Deque a) m) => Int -> m (Deque a) take = reader . Deque.take -{-|-\(\mathcal{O}(n)\).-Drop the specified amount of first elements.--}-drop :: MonadReader (Deque a) m => Int -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Drop the specified amount of first elements.+drop :: (MonadReader (Deque a) m) => Int -> m (Deque a) drop = reader . Deque.drop -{-|-\(\mathcal{O}(n)\).-Leave only the first elements satisfying the predicate.--}-takeWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the first elements satisfying the predicate.+takeWhile :: (MonadReader (Deque a) m) => (a -> Bool) -> m (Deque a) takeWhile predicate = reader (Deque.takeWhile predicate) -{-|-\(\mathcal{O}(n)\).-Drop the first elements satisfying the predicate.--}-dropWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Drop the first elements satisfying the predicate.+dropWhile :: (MonadReader (Deque a) m) => (a -> Bool) -> m (Deque a) dropWhile predicate = reader (Deque.dropWhile predicate) -{-|-\(\mathcal{O}(n)\).-Same as @(,) '<$>' `takeWhile` predicate '<*>' `dropWhile` predicate@.--}-span :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a, Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Same as @(,) '<$>' `takeWhile` predicate '<*>' `dropWhile` predicate@.+span :: (MonadReader (Deque a) m) => (a -> Bool) -> m (Deque a, Deque a) span predicate = reader (Deque.span predicate) -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-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))+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{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)+ ) -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{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))+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{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)+ ) -{-|-\(\mathcal{O}(1)\). -Check whether deque is empty.--}-null :: MonadReader (Deque a) m => m Bool+-- |+-- \(\mathcal{O}(1)\).+-- Check whether deque is empty.+null :: (MonadReader (Deque a) m) => m Bool null = reader Deque.null -{-|-\(\mathcal{O}(1)\). -Check whether deque is empty.--}-length :: MonadReader (Deque a) m => m Int+-- |+-- \(\mathcal{O}(1)\).+-- Check whether deque is empty.+length :: (MonadReader (Deque a) m) => m Int length = reader Prelude.length -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the first element if deque is not empty.--}-head :: MonadReader (Deque a) m => m (Maybe a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the first element if deque is not empty.+head :: (MonadReader (Deque a) m) => m (Maybe a) head = reader Deque.head -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the last element if deque is not empty.--}-last :: MonadReader (Deque a) m => m (Maybe a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the last element if deque is not empty.+last :: (MonadReader (Deque a) m) => m (Maybe a) last = reader Deque.last -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Keep all elements but the first one.--}-tail :: MonadReader (Deque a) m => m (Deque a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Keep all elements but the first one.+tail :: (MonadReader (Deque a) m) => m (Deque a) tail = reader Deque.tail -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Keep all elements but the last one.--}-init :: MonadReader (Deque a) m => m (Deque a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Keep all elements but the last one.+init :: (MonadReader (Deque a) m) => m (Deque a) init = reader Deque.init
library/Deque/Lazy/State.hs view
@@ -1,171 +1,152 @@-{-|-Lazy Deque API lifted to a State monad, \"mtl\"-style.--}-module Deque.Lazy.State-where+-- |+-- 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 Deque.Prelude hiding (dropWhile, head, init, last, null, reverse, tail, takeWhile) import qualified Deque.Prelude as Prelude --{-|-\(\mathcal{O}(n)\).-Modify each element of the queue.--}-map :: MonadState (Deque a) m => (a -> a) -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Modify each element of the queue.+map :: (MonadState (Deque a) m) => (a -> a) -> m () map f = modify (fmap f) -{-|-\(\mathcal{O}(n)\).-Add elements to the begginning.--}-prepend :: MonadState (Deque a) m => Deque a -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Add elements to the begginning.+prepend :: (MonadState (Deque a) m) => Deque a -> m () prepend deque = modify (deque <>) -{-|-\(\mathcal{O}(n)\).-Add elements to the ending.--}-append :: MonadState (Deque a) m => Deque a -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Add elements to the ending.+append :: (MonadState (Deque a) m) => Deque a -> m () append deque = modify (<> deque) -{-|-\(\mathcal{O}(1)\).-Add element in the beginning.--}-cons :: MonadState (Deque a) m => a -> m ()+-- |+-- \(\mathcal{O}(1)\).+-- Add element in the beginning.+cons :: (MonadState (Deque a) m) => a -> m () cons a = modify (Deque.cons a) -{-|-\(\mathcal{O}(1)\).-Add element in the ending.--}-snoc :: MonadState (Deque a) m => a -> m ()+-- |+-- \(\mathcal{O}(1)\).+-- Add element in the ending.+snoc :: (MonadState (Deque a) m) => a -> m () snoc a = modify (Deque.snoc a) -{-|-\(\mathcal{O}(1)\).-Reverse the deque.--}-reverse :: MonadState (Deque a) m => m ()+-- |+-- \(\mathcal{O}(1)\).+-- Reverse the deque.+reverse :: (MonadState (Deque a) m) => m () reverse = modify Deque.reverse -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Move the first element to the end.--}-shiftLeft :: MonadState (Deque a) m => m ()+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Move the first element to the end.+shiftLeft :: (MonadState (Deque a) m) => m () shiftLeft = modify Deque.shiftLeft -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Move the last element to the beginning.--}-shiftRight :: MonadState (Deque a) m => m ()+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Move the last element to the beginning.+shiftRight :: (MonadState (Deque a) m) => m () shiftRight = modify Deque.shiftRight -{-|-\(\mathcal{O}(n)\).-Leave only the elements satisfying the predicate.--}-filter :: MonadState (Deque a) m => (a -> Bool) -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the elements satisfying the predicate.+filter :: (MonadState (Deque a) m) => (a -> Bool) -> m () filter predicate = modify (Deque.filter predicate) -{-|-\(\mathcal{O}(n)\).-Leave only the specified amount of first elements.--}-take :: MonadState (Deque a) m => Int -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the specified amount of first elements.+take :: (MonadState (Deque a) m) => Int -> m () take = modify . Deque.take -{-|-\(\mathcal{O}(n)\).-Drop the specified amount of first elements.--}-drop :: MonadState (Deque a) m => Int -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Drop the specified amount of first elements.+drop :: (MonadState (Deque a) m) => Int -> m () drop = modify . Deque.drop -{-|-\(\mathcal{O}(n)\).-Leave only the first elements satisfying the predicate.--}-takeWhile :: MonadState (Deque a) m => (a -> Bool) -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the first elements satisfying the predicate.+takeWhile :: (MonadState (Deque a) m) => (a -> Bool) -> m () takeWhile predicate = modify (Deque.takeWhile predicate) -{-|-\(\mathcal{O}(n)\).-Drop the first elements satisfying the predicate.--}-dropWhile :: MonadState (Deque a) m => (a -> Bool) -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Drop the first elements satisfying the predicate.+dropWhile :: (MonadState (Deque a) m) => (a -> Bool) -> m () dropWhile predicate = modify (Deque.dropWhile predicate) -{-|-\(\mathcal{O}(n)\).-Return the first elements satisfying the predicate, removing them from the state.--}-span :: MonadState (Deque a) m => (a -> Bool) -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Return the first elements satisfying the predicate, removing them from the state.+span :: (MonadState (Deque a) m) => (a -> Bool) -> m (Deque a) span predicate = state (Deque.span predicate) -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the first element if deque is not empty,-removing the element.--}-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))+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the first element if deque is not empty,+-- removing the element.+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)+ ) -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the last element if deque is not empty,-removing the element.--}-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))+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the last element if deque is not empty,+-- removing the element.+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)+ ) -{-|-\(\mathcal{O}(1)\). -Check whether deque is empty.--}-null :: MonadState (Deque a) m => m Bool+-- |+-- \(\mathcal{O}(1)\).+-- Check whether deque is empty.+null :: (MonadState (Deque a) m) => m Bool null = gets Deque.null -{-|-\(\mathcal{O}(1)\). -Check whether deque is empty.--}-length :: MonadState (Deque a) m => m Int+-- |+-- \(\mathcal{O}(1)\).+-- Check whether deque is empty.+length :: (MonadState (Deque a) m) => m Int length = gets Prelude.length -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the first element if deque is not empty.--}-head :: MonadState (Deque a) m => m (Maybe a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the first element if deque is not empty.+head :: (MonadState (Deque a) m) => m (Maybe a) head = gets Deque.head -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the last element if deque is not empty.--}-last :: MonadState (Deque a) m => m (Maybe a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the last element if deque is not empty.+last :: (MonadState (Deque a) m) => m (Maybe a) last = gets Deque.last -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Keep all elements but the first one.--}-tail :: MonadState (Deque a) m => m ()+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Keep all elements but the first one.+tail :: (MonadState (Deque a) m) => m () tail = modify Deque.tail -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Keep all elements but the last one.--}-init :: MonadState (Deque a) m => m ()+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Keep all elements but the last one.+init :: (MonadState (Deque a) m) => m () init = modify Deque.init
library/Deque/Prelude.hs view
@@ -1,22 +1,24 @@ module Deque.Prelude-(- module Exports,-)+ ( 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.DeepSeq 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 as Exports hiding (fail, forM, forM_, mapM, mapM_, msum, sequence, sequence_)+import Control.Monad.Cont.Class as Exports+import Control.Monad.Error.Class as Exports import Control.Monad.Fail as Exports import Control.Monad.Fix as Exports hiding (fix)+import Control.Monad.IO.Class as Exports+import Control.Monad.Reader.Class as Exports import Control.Monad.ST as Exports+import Control.Monad.State.Class as Exports+import Control.Monad.Writer.Class as Exports import Data.Bits as Exports import Data.Bool as Exports import Data.Char as Exports@@ -28,19 +30,20 @@ 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 as Exports hiding (unzip) import Data.Functor.Identity as Exports-import Data.Int as Exports+import Data.Hashable as Exports (Hashable) import Data.IORef as Exports+import Data.Int 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.List as Exports hiding (all, and, any, concat, concatMap, elem, find, foldl, foldl', foldl1, foldr, foldr1, isSubsequenceOf, mapAccumL, mapAccumR, maximum, maximumBy, minimum, minimumBy, notElem, or, product, sortOn, sum, uncons, unsnoc) import Data.Maybe as Exports-import Data.Monoid as Exports hiding (Last(..), First(..), (<>))+import Data.Monoid as Exports hiding (First (..), Last (..), (<>)) 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.Semigroup as Exports import Data.String as Exports import Data.Traversable as Exports import Data.Tuple as Exports@@ -51,13 +54,12 @@ 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 Foreign.Storable as Exports hiding (alignment, sizeOf)+import GHC.Conc as Exports hiding (threadWaitRead, threadWaitReadSTM, threadWaitWrite, threadWaitWriteSTM, withMVar)+import GHC.Exts as Exports (IsList (..), groupWith, inline, lazy, sortWith) 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@@ -66,24 +68,7 @@ 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 Text.Printf as Exports (hPrintf, printf)+import Text.Read as Exports (Read (..), readEither, readMaybe) import Unsafe.Coerce as Exports---- mtl---------------------------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)---- hashable---------------------------import Data.Hashable as Exports (Hashable)---- deepseq---------------------------import Control.DeepSeq as Exports+import Prelude as Exports hiding (all, and, any, concat, concatMap, elem, fail, foldl, foldl1, foldr, foldr1, id, mapM, mapM_, maximum, minimum, notElem, or, product, sequence, sequence_, sum, (.))
library/Deque/Strict.hs view
@@ -1,44 +1,42 @@-{-|-Definitions of strict Deque.--The typical `toList` and `fromList` conversions are provided by means of-the `Foldable` and `IsList` instances.--}+-- |+-- Definitions of strict Deque.+--+-- The typical `toList` and `fromList` conversions are provided by means of+-- the `Foldable` and `IsList` instances. module Deque.Strict-(- 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.span,- StrictDefs.uncons,- StrictDefs.unsnoc,- StrictDefs.null,- StrictDefs.head,- StrictDefs.last,- StrictDefs.tail,- StrictDefs.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.span,+ StrictDefs.uncons,+ StrictDefs.unsnoc,+ StrictDefs.null,+ StrictDefs.head,+ StrictDefs.last,+ StrictDefs.tail,+ StrictDefs.init,+ ) where -import Deque.Prelude import qualified Deque.Lazy.Defs as LazyDefs+import Deque.Prelude import qualified Deque.Strict.Defs as StrictDefs -{-| Convert lazy deque to strict deque. -}+-- | Convert lazy deque to strict deque. fromLazy :: LazyDefs.Deque a -> StrictDefs.Deque a fromLazy (LazyDefs.Deque consList snocList) = StrictDefs.Deque (fromList consList) (fromList snocList) -{-| Convert strict deque to lazy deque. -}+-- | Convert strict deque to lazy deque. toLazy :: StrictDefs.Deque a -> LazyDefs.Deque a toLazy (StrictDefs.Deque consList snocList) = LazyDefs.Deque (toList consList) (toList snocList)
library/Deque/Strict/Defs.hs view
@@ -1,17 +1,15 @@ {-# LANGUAGE CPP #-}-{-|-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+-- |+-- 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+import Deque.Prelude hiding (dropWhile, filter, head, init, last, null, reverse, tail, take, takeWhile) import qualified Deque.Prelude as Prelude+import qualified StrictList -- | -- Strict double-ended queue (aka Dequeue or Deque) based on head-tail linked list.@@ -20,24 +18,28 @@ -- | -- \(\mathcal{O}(n)\). -- Construct from cons and snoc lists.+{-# INLINE fromConsAndSnocLists #-} fromConsAndSnocLists :: [a] -> [a] -> Deque a fromConsAndSnocLists consList snocList = Deque (fromList consList) (fromList snocList) -- | -- \(\mathcal{O}(1)\). -- Add element in the beginning.+{-# INLINE cons #-} cons :: a -> Deque a -> Deque a cons a (Deque consList snocList) = Deque (StrictList.Cons a consList) snocList -- | -- \(\mathcal{O}(1)\). -- Add element in the ending.+{-# INLINE snoc #-} snoc :: a -> Deque a -> Deque a snoc a (Deque consList snocList) = Deque consList (StrictList.Cons a snocList) -- | -- \(\mathcal{O}(1)\). -- Reverse the deque.+{-# INLINE reverse #-} reverse :: Deque a -> Deque a reverse (Deque consList snocList) = Deque snocList consList @@ -49,6 +51,7 @@ -- λ toList . shiftLeft $ fromList [1,2,3] -- [2,3,1] -- @+{-# INLINE shiftLeft #-} shiftLeft :: Deque a -> Deque a shiftLeft deque = maybe deque (uncurry snoc) (uncons deque) @@ -60,6 +63,7 @@ -- λ toList . shiftRight $ fromList [1,2,3] -- [3,1,2] -- @+{-# INLINE shiftRight #-} shiftRight :: Deque a -> Deque a shiftRight deque = maybe deque (uncurry cons) (unsnoc deque) @@ -69,91 +73,104 @@ -- | -- \(\mathcal{O}(n)\). -- Leave only the elements satisfying the predicate.+{-# INLINE filter #-} 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+filter predicate (Deque consList snocList) =+ let newConsList =+ StrictList.prependReversed+ (StrictList.filterReversed predicate consList)+ (StrictList.filterReversed predicate snocList)+ in Deque newConsList StrictList.Nil -- | -- \(\mathcal{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+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 -- | -- \(\mathcal{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+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 -- | -- \(\mathcal{O}(n)\). -- Leave only the first elements satisfying the predicate.+{-# INLINE takeWhile #-} 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+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 -- | -- \(\mathcal{O}(n)\). -- Drop the first elements satisfying the predicate.+{-# INLINE dropWhile #-} 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+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 -- | -- \(\mathcal{O}(n)\). -- Perform `takeWhile` and `dropWhile` in a single operation. span :: (a -> Bool) -> Deque a -> (Deque a, Deque a) span predicate (Deque consList snocList) = case StrictList.spanReversed predicate consList of- (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)+ (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) -- | -- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the first element and deque without it if it's not empty.+{-# INLINE uncons #-} uncons :: Deque a -> Maybe (a, Deque a) uncons (Deque consList snocList) = case consList of StrictList.Cons head tail -> Just (head, Deque tail snocList)@@ -164,6 +181,7 @@ -- | -- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the last element and deque without it if it's not empty.+{-# INLINE unsnoc #-} unsnoc :: Deque a -> Maybe (a, Deque a) unsnoc (Deque consList snocList) = case snocList of StrictList.Cons head tail -> Just (head, Deque consList tail)@@ -172,16 +190,18 @@ _ -> Nothing -- |--- \(\mathcal{O}(1)\). +-- \(\mathcal{O}(1)\). -- Check whether deque is empty.+{-# INLINE null #-} null :: Deque a -> Bool-null = \ case+null = \case Deque StrictList.Nil StrictList.Nil -> True _ -> False -- | -- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the first element if deque is not empty.+{-# INLINE head #-} head :: Deque a -> Maybe a head (Deque consList snocList) = case consList of StrictList.Cons head _ -> Just head@@ -190,6 +210,7 @@ -- | -- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Get the last element if deque is not empty.+{-# INLINE last #-} last :: Deque a -> Maybe a last (Deque consList snocList) = case snocList of StrictList.Cons head _ -> Just head@@ -198,8 +219,9 @@ -- | -- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Keep all elements but the first one.--- +-- -- In case of empty deque returns an empty deque.+{-# INLINE tail #-} tail :: Deque a -> Deque a tail (Deque consList snocList) = case consList of StrictList.Cons _ consListTail -> Deque consListTail snocList@@ -208,18 +230,18 @@ -- | -- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\). -- Keep all elements but the last one.--- +-- -- In case of empty deque returns an empty deque.+{-# INLINE init #-} 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+instance (Eq a) => Eq (Deque a) where (==) a b = toList a == toList b -instance Show a => Show (Deque a) where+instance (Show a) => Show (Deque a) where show = show . toList instance IsList (Deque a) where@@ -228,10 +250,10 @@ toList (Deque consList snocList) = foldr (:) (toList (StrictList.reverse snocList)) consList instance Semigroup (Deque a) where- (<>) (Deque consList1 snocList1) (Deque consList2 snocList2) = let- consList = consList1- snocList = snocList2 <> StrictList.prependReversed consList2 snocList1- in Deque consList snocList+ (<>) (Deque consList1 snocList1) (Deque consList2 snocList2) =+ let consList = consList1+ snocList = snocList2 <> StrictList.prependReversed consList2 snocList1+ in Deque consList snocList instance Monoid (Deque a) where mempty = Deque StrictList.Nil StrictList.Nil@@ -249,22 +271,22 @@ instance Applicative Deque where pure a = Deque (pure a) StrictList.Nil- (<*>) (Deque fnConsList fnSnocList) (Deque argConsList argSnocList) = let- snocList = let- fnStep resultSnocList fn = let- argStep resultSnocList arg = StrictList.Cons (fn arg) resultSnocList- in foldl' argStep (foldl' argStep resultSnocList argConsList) (StrictList.reverse argSnocList)- in foldl' fnStep (foldl' fnStep StrictList.Nil fnConsList) (StrictList.reverse fnSnocList)- in Deque StrictList.Nil snocList+ (<*>) (Deque fnConsList fnSnocList) (Deque argConsList argSnocList) =+ let snocList =+ let fnStep resultSnocList fn =+ let argStep resultSnocList arg = StrictList.Cons (fn arg) resultSnocList+ in foldl' argStep (foldl' argStep resultSnocList argConsList) (StrictList.reverse argSnocList)+ in foldl' fnStep (foldl' fnStep StrictList.Nil fnConsList) (StrictList.reverse fnSnocList)+ in Deque StrictList.Nil snocList instance Monad Deque where return = pure- (>>=) (Deque aConsList aSnocList) k = let- snocList = let- aStep accBSnocList a = case k a of- Deque bConsList bSnocList -> StrictList.prependReversed bConsList (bSnocList <> accBSnocList)- in foldl' aStep (foldl' aStep StrictList.Nil aConsList) (StrictList.reverse aSnocList)- in Deque StrictList.Nil snocList+ (>>=) (Deque aConsList aSnocList) k =+ let snocList =+ let aStep accBSnocList a = case k a of+ Deque bConsList bSnocList -> StrictList.prependReversed bConsList (bSnocList <> accBSnocList)+ in foldl' aStep (foldl' aStep StrictList.Nil aConsList) (StrictList.reverse aSnocList)+ in Deque StrictList.Nil snocList #if !(MIN_VERSION_base(4,13,0)) fail = const mempty #endif@@ -281,9 +303,11 @@ fail = const mempty deriving instance Generic (Deque a)+ deriving instance Generic1 Deque -instance Hashable a => Hashable (Deque a)+instance (Hashable a) => Hashable (Deque a) -instance NFData a => NFData (Deque a)+instance (NFData a) => NFData (Deque a)+ instance NFData1 Deque
library/Deque/Strict/Reader.hs view
@@ -1,169 +1,150 @@-{-|-Strict Deque API lifted to a Reader monad, \"mtl\"-style.--}-module Deque.Strict.Reader-where+-- |+-- 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.Prelude hiding (dropWhile, head, init, last, null, reverse, tail, takeWhile)+import qualified Deque.Prelude as Prelude import Deque.Strict (Deque) import qualified Deque.Strict as Deque-import qualified Deque.Prelude as Prelude --{-|-\(\mathcal{O}(n)\).-Modify each element of the queue.--}-map :: MonadReader (Deque a) m => (a -> b) -> m (Deque b)+-- |+-- \(\mathcal{O}(n)\).+-- Modify each element of the queue.+map :: (MonadReader (Deque a) m) => (a -> b) -> m (Deque b) map f = reader (fmap f) -{-|-\(\mathcal{O}(n)\).-Add elements to the begginning.--}-prepend :: MonadReader (Deque a) m => Deque a -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Add elements to the begginning.+prepend :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) prepend deque = reader (deque <>) -{-|-\(\mathcal{O}(n)\).-Add elements to the ending.--}-append :: MonadReader (Deque a) m => Deque a -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Add elements to the ending.+append :: (MonadReader (Deque a) m) => Deque a -> m (Deque a) append deque = reader (<> deque) -{-|-\(\mathcal{O}(1)\).-Add element in the beginning.--}-cons :: MonadReader (Deque a) m => a -> m (Deque a)+-- |+-- \(\mathcal{O}(1)\).+-- Add element in the beginning.+cons :: (MonadReader (Deque a) m) => a -> m (Deque a) cons a = reader (Deque.cons a) -{-|-\(\mathcal{O}(1)\).-Add element in the ending.--}-snoc :: MonadReader (Deque a) m => a -> m (Deque a)+-- |+-- \(\mathcal{O}(1)\).+-- Add element in the ending.+snoc :: (MonadReader (Deque a) m) => a -> m (Deque a) snoc a = reader (Deque.snoc a) -{-|-\(\mathcal{O}(1)\).-Reverse the deque.--}-reverse :: MonadReader (Deque a) m => m (Deque a)+-- |+-- \(\mathcal{O}(1)\).+-- Reverse the deque.+reverse :: (MonadReader (Deque a) m) => m (Deque a) reverse = reader Deque.reverse -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Move the first element to the end.--}-shiftLeft :: MonadReader (Deque a) m => m (Deque a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Move the first element to the end.+shiftLeft :: (MonadReader (Deque a) m) => m (Deque a) shiftLeft = reader Deque.shiftLeft -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Move the last element to the beginning.--}-shiftRight :: MonadReader (Deque a) m => m (Deque a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Move the last element to the beginning.+shiftRight :: (MonadReader (Deque a) m) => m (Deque a) shiftRight = reader Deque.shiftRight -{-|-\(\mathcal{O}(n)\).-Leave only the elements satisfying the predicate.--}-filter :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the elements satisfying the predicate.+filter :: (MonadReader (Deque a) m) => (a -> Bool) -> m (Deque a) filter predicate = reader (Deque.filter predicate) -{-|-\(\mathcal{O}(n)\).-Leave only the specified amount of first elements.--}-take :: MonadReader (Deque a) m => Int -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the specified amount of first elements.+take :: (MonadReader (Deque a) m) => Int -> m (Deque a) take = reader . Deque.take -{-|-\(\mathcal{O}(n)\).-Drop the specified amount of first elements.--}-drop :: MonadReader (Deque a) m => Int -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Drop the specified amount of first elements.+drop :: (MonadReader (Deque a) m) => Int -> m (Deque a) drop = reader . Deque.drop -{-|-\(\mathcal{O}(n)\).-Leave only the first elements satisfying the predicate.--}-takeWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the first elements satisfying the predicate.+takeWhile :: (MonadReader (Deque a) m) => (a -> Bool) -> m (Deque a) takeWhile predicate = reader (Deque.takeWhile predicate) -{-|-\(\mathcal{O}(n)\).-Drop the first elements satisfying the predicate.--}-dropWhile :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Drop the first elements satisfying the predicate.+dropWhile :: (MonadReader (Deque a) m) => (a -> Bool) -> m (Deque a) dropWhile predicate = reader (Deque.dropWhile predicate) -{-|-\(\mathcal{O}(n)\).-Same as @(,) '<$>' `takeWhile` predicate '<*>' `dropWhile` predicate@.--}-span :: MonadReader (Deque a) m => (a -> Bool) -> m (Deque a, Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Same as @(,) '<$>' `takeWhile` predicate '<*>' `dropWhile` predicate@.+span :: (MonadReader (Deque a) m) => (a -> Bool) -> m (Deque a, Deque a) span predicate = reader (Deque.span predicate) -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-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))+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{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)+ ) -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{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))+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{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)+ ) -{-|-\(\mathcal{O}(1)\). -Check whether deque is empty.--}-null :: MonadReader (Deque a) m => m Bool+-- |+-- \(\mathcal{O}(1)\).+-- Check whether deque is empty.+null :: (MonadReader (Deque a) m) => m Bool null = reader Deque.null -{-|-\(\mathcal{O}(1)\). -Check whether deque is empty.--}-length :: MonadReader (Deque a) m => m Int+-- |+-- \(\mathcal{O}(1)\).+-- Check whether deque is empty.+length :: (MonadReader (Deque a) m) => m Int length = reader Prelude.length -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the first element if deque is not empty.--}-head :: MonadReader (Deque a) m => m (Maybe a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the first element if deque is not empty.+head :: (MonadReader (Deque a) m) => m (Maybe a) head = reader Deque.head -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the last element if deque is not empty.--}-last :: MonadReader (Deque a) m => m (Maybe a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the last element if deque is not empty.+last :: (MonadReader (Deque a) m) => m (Maybe a) last = reader Deque.last -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Keep all elements but the first one.--}-tail :: MonadReader (Deque a) m => m (Deque a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Keep all elements but the first one.+tail :: (MonadReader (Deque a) m) => m (Deque a) tail = reader Deque.tail -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Keep all elements but the last one.--}-init :: MonadReader (Deque a) m => m (Deque a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Keep all elements but the last one.+init :: (MonadReader (Deque a) m) => m (Deque a) init = reader Deque.init
library/Deque/Strict/State.hs view
@@ -1,171 +1,152 @@-{-|-Strict Deque API lifted to a State monad, \"mtl\"-style.--}-module Deque.Strict.State-where+-- |+-- 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.Prelude hiding (dropWhile, head, init, last, null, reverse, tail, takeWhile)+import qualified Deque.Prelude as Prelude import Deque.Strict (Deque) import qualified Deque.Strict as Deque-import qualified Deque.Prelude as Prelude --{-|-\(\mathcal{O}(n)\).-Modify each element of the queue.--}-map :: MonadState (Deque a) m => (a -> a) -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Modify each element of the queue.+map :: (MonadState (Deque a) m) => (a -> a) -> m () map f = modify (fmap f) -{-|-\(\mathcal{O}(n)\).-Add elements to the begginning.--}-prepend :: MonadState (Deque a) m => Deque a -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Add elements to the begginning.+prepend :: (MonadState (Deque a) m) => Deque a -> m () prepend deque = modify (deque <>) -{-|-\(\mathcal{O}(n)\).-Add elements to the ending.--}-append :: MonadState (Deque a) m => Deque a -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Add elements to the ending.+append :: (MonadState (Deque a) m) => Deque a -> m () append deque = modify (<> deque) -{-|-\(\mathcal{O}(1)\).-Add element in the beginning.--}-cons :: MonadState (Deque a) m => a -> m ()+-- |+-- \(\mathcal{O}(1)\).+-- Add element in the beginning.+cons :: (MonadState (Deque a) m) => a -> m () cons a = modify (Deque.cons a) -{-|-\(\mathcal{O}(1)\).-Add element in the ending.--}-snoc :: MonadState (Deque a) m => a -> m ()+-- |+-- \(\mathcal{O}(1)\).+-- Add element in the ending.+snoc :: (MonadState (Deque a) m) => a -> m () snoc a = modify (Deque.snoc a) -{-|-\(\mathcal{O}(1)\).-Reverse the deque.--}-reverse :: MonadState (Deque a) m => m ()+-- |+-- \(\mathcal{O}(1)\).+-- Reverse the deque.+reverse :: (MonadState (Deque a) m) => m () reverse = modify Deque.reverse -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Move the first element to the end.--}-shiftLeft :: MonadState (Deque a) m => m ()+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Move the first element to the end.+shiftLeft :: (MonadState (Deque a) m) => m () shiftLeft = modify Deque.shiftLeft -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Move the last element to the beginning.--}-shiftRight :: MonadState (Deque a) m => m ()+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Move the last element to the beginning.+shiftRight :: (MonadState (Deque a) m) => m () shiftRight = modify Deque.shiftRight -{-|-\(\mathcal{O}(n)\).-Leave only the elements satisfying the predicate.--}-filter :: MonadState (Deque a) m => (a -> Bool) -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the elements satisfying the predicate.+filter :: (MonadState (Deque a) m) => (a -> Bool) -> m () filter predicate = modify (Deque.filter predicate) -{-|-\(\mathcal{O}(n)\).-Leave only the specified amount of first elements.--}-take :: MonadState (Deque a) m => Int -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the specified amount of first elements.+take :: (MonadState (Deque a) m) => Int -> m () take = modify . Deque.take -{-|-\(\mathcal{O}(n)\).-Drop the specified amount of first elements.--}-drop :: MonadState (Deque a) m => Int -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Drop the specified amount of first elements.+drop :: (MonadState (Deque a) m) => Int -> m () drop = modify . Deque.drop -{-|-\(\mathcal{O}(n)\).-Leave only the first elements satisfying the predicate.--}-takeWhile :: MonadState (Deque a) m => (a -> Bool) -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Leave only the first elements satisfying the predicate.+takeWhile :: (MonadState (Deque a) m) => (a -> Bool) -> m () takeWhile predicate = modify (Deque.takeWhile predicate) -{-|-\(\mathcal{O}(n)\).-Drop the first elements satisfying the predicate.--}-dropWhile :: MonadState (Deque a) m => (a -> Bool) -> m ()+-- |+-- \(\mathcal{O}(n)\).+-- Drop the first elements satisfying the predicate.+dropWhile :: (MonadState (Deque a) m) => (a -> Bool) -> m () dropWhile predicate = modify (Deque.dropWhile predicate) -{-|-\(\mathcal{O}(n)\).-Return the first elements satisfying the predicate, removing them from the state.--}-span :: MonadState (Deque a) m => (a -> Bool) -> m (Deque a)+-- |+-- \(\mathcal{O}(n)\).+-- Return the first elements satisfying the predicate, removing them from the state.+span :: (MonadState (Deque a) m) => (a -> Bool) -> m (Deque a) span predicate = state (Deque.span predicate) -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the first element if deque is not empty,-removing the element.--}-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))+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the first element if deque is not empty,+-- removing the element.+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)+ ) -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the last element if deque is not empty,-removing the element.--}-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))+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the last element if deque is not empty,+-- removing the element.+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)+ ) -{-|-\(\mathcal{O}(1)\). -Check whether deque is empty.--}-null :: MonadState (Deque a) m => m Bool+-- |+-- \(\mathcal{O}(1)\).+-- Check whether deque is empty.+null :: (MonadState (Deque a) m) => m Bool null = gets Deque.null -{-|-\(\mathcal{O}(1)\). -Check whether deque is empty.--}-length :: MonadState (Deque a) m => m Int+-- |+-- \(\mathcal{O}(1)\).+-- Check whether deque is empty.+length :: (MonadState (Deque a) m) => m Int length = gets Prelude.length -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the first element if deque is not empty.--}-head :: MonadState (Deque a) m => m (Maybe a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the first element if deque is not empty.+head :: (MonadState (Deque a) m) => m (Maybe a) head = gets Deque.head -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Get the last element if deque is not empty.--}-last :: MonadState (Deque a) m => m (Maybe a)+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Get the last element if deque is not empty.+last :: (MonadState (Deque a) m) => m (Maybe a) last = gets Deque.last -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Keep all elements but the first one.--}-tail :: MonadState (Deque a) m => m ()+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Keep all elements but the first one.+tail :: (MonadState (Deque a) m) => m () tail = modify Deque.tail -{-|-\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).-Keep all elements but the last one.--}-init :: MonadState (Deque a) m => m ()+-- |+-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).+-- Keep all elements but the last one.+init :: (MonadState (Deque a) m) => m () init = modify Deque.init
test/Main.hs view
@@ -1,164 +1,176 @@+{-# OPTIONS_GHC -Wno-orphans -Wno-missing-signatures #-}+ module Main where -import Prelude hiding (toList, choose)-import GHC.Exts as Exports (IsList(..))-import Test.QuickCheck.Instances-import Test.Tasty-import Test.Tasty.Runners-import Test.Tasty.HUnit-import Test.Tasty.QuickCheck-import qualified Test.QuickCheck as QuickCheck-import qualified Test.QuickCheck.Property as QuickCheck import qualified Data.List as List import qualified Deque.Lazy as Lazy import qualified Deque.Strict as Strict-+import GHC.Exts as Exports (IsList (..))+import Test.Tasty+import Test.Tasty.QuickCheck+import Prelude hiding (choose, toList) main =- defaultMain $- testGroup "" $- [- 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.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.span- 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+ defaultMain+ $ testGroup ""+ $ [ 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.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.span+ 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+ ]+ ] ]- ]- ] -{-|-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 take drop takeWhile dropWhile span- 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 === 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 "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- ,- 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- ,- 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 "<>" $ forAll ((,) <$> dequeAndListGen <*> dequeAndListGen) $ \ ((deque1, list1), (deque2, list2)) ->- toList (deque1 <> deque2) === (list1 <> list2)- ,- testProperty "<*>" $ forAll ((,) <$> dequeAndListGen <*> dequeAndListGen) $ \ ((deque1, list1), (deque2, list2)) ->- toList ((,) <$> deque1 <*> deque2) === ((,) <$> list1 <*> list2)- ,- testProperty ">>=" $ forAll ((,) <$> dequeAndListKleisliGen <*> dequeAndListGen) $ \ ((dequeK, listK), (deque, list)) ->- toList (deque >>= dequeK) === (list >>= listK)- ,- testProperty "foldl'" $ forAll dequeAndListGen $ \ (deque, list) ->- foldl' (flip (:)) [] deque === foldl' (flip (:)) [] list- ,- 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- ]+-- |+-- 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+ take+ drop+ takeWhile+ dropWhile+ span+ 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 === 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 "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,+ 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,+ 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 "<>" $ forAll ((,) <$> dequeAndListGen <*> dequeAndListGen) $ \((deque1, list1), (deque2, list2)) ->+ toList (deque1 <> deque2) === (list1 <> list2),+ testProperty "<*>" $ forAll ((,) <$> dequeAndListGen <*> dequeAndListGen) $ \((deque1, list1), (deque2, list2)) ->+ toList ((,) <$> deque1 <*> deque2) === ((,) <$> list1 <*> list2),+ testProperty ">>=" $ forAll ((,) <$> dequeAndListKleisliGen <*> dequeAndListGen) $ \((dequeK, listK), (deque, list)) ->+ toList (deque >>= dequeK) === (list >>= listK),+ testProperty "foldl'" $ forAll dequeAndListGen $ \(deque, list) ->+ foldl' (flip (:)) [] deque === foldl' (flip (:)) [] list,+ 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 dequeAndListGen = do consList <- listGen@@ -166,10 +178,9 @@ return (fromConsAndSnocLists consList snocList, consList <> List.reverse snocList) dequeAndListKleisliGen = do list <- listGen- let- listK x = fmap (+ x) list- dequeK = fromList . listK- in return (dequeK, listK)+ let listK x = fmap (+ x) list+ dequeK = fromList . listK+ in return (dequeK, listK) sizedListGen maxSize = do length <- choose (0, maxSize)@@ -187,8 +198,7 @@ snocList <- listGen return (Strict.fromConsAndSnocLists consList snocList, Lazy.fromConsAndSnocLists consList snocList) ---- * Workarounds to satisfy QuickCheck's requirements,+-- Workarounds to satisfy QuickCheck's requirements, -- when we need to generate a predicate. -------------------------