deque 0.1 → 0.2

raw patch · 2 files changed

+72/−26 lines, 2 filesdep −base-preludedep ~basePVP ok

version bump matches the API change (PVP)

Dependencies removed: base-prelude

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• deque.cabal +6/−8
• library/Deque.hs +66/−18

@@ -1,16 +1,16 @@ name:   deque version:-  0.1+  0.2 synopsis:   Double-ended queue description:-  An implementation of double-ended queue (aka Dequeue or Deque)+  An implementation of Double-Ended Queue (aka Dequeue or Deque)   based on the head-tail linked list. homepage:-  https://github.com/nikita-volkov/deque +  https://github.com/nikita-volkov/deque bug-reports:-  https://github.com/nikita-volkov/deque/issues +  https://github.com/nikita-volkov/deque/issues author:   Nikita Volkov <nikita.y.volkov@mail.ru> maintainer:@@ -26,22 +26,20 @@ cabal-version:   >=1.10 - source-repository head   type:     git   location:     git://github.com/nikita-volkov/deque.git - library   hs-source-dirs:     library   default-extensions:-    Arrows, BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedStrings, PatternGuards, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, TemplateHaskell, TupleSections, TypeFamilies, TypeOperators, UnboxedTuples+    DeriveFunctor, StandaloneDeriving   default-language:     Haskell2010   exposed-modules:     Deque   build-depends:-    base-prelude < 2+    base >= 4.6 && < 5

@@ -1,45 +1,61 @@ module Deque where -import BasePrelude hiding (uncons, unsnoc, cons, snoc, reverse)-import qualified BasePrelude+import Prelude hiding (foldr, foldr', foldl')+import Control.Applicative+import Data.Foldable+import Data.Traversable+import Data.Maybe+import Data.Monoid  +-- |+-- 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 list =-  Deque [] list+fromList =+  Deque []  -- | -- /O(1)/, occasionally /O(n)/.-shiftRight :: Deque a -> Deque a-shiftRight deque =-  fromMaybe deque $-  fmap (\(a, b) -> snoc a b) $-  uncons deque+--+-- @+-- λ 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)/.-shiftLeft :: Deque a -> Deque a-shiftLeft deque =-  fromMaybe deque $-  fmap (\(a, b) -> cons a b) $-  unsnoc deque+--+-- @+-- λ 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)+  Deque snocList (a : consList)  -- | -- /O(1)/.+-- Append an element. snoc :: a -> Deque a -> Deque a snoc a (Deque snocList consList) =-  Deque (a : snocList) (consList)+  Deque (a : snocList) consList  -- | -- /O(1)/, occasionally /O(n)/.@@ -49,7 +65,7 @@     head : tail ->       Just (head, Deque snocList tail)     _ ->-      case BasePrelude.reverse snocList of+      case Prelude.reverse snocList of         head : tail ->           Just (head, Deque [] tail)         _ ->@@ -63,7 +79,7 @@     head : tail ->       Just (head, Deque tail consList)     _ ->-      case BasePrelude.reverse consList of+      case Prelude.reverse consList of         head : tail ->           Just (head, Deque tail [])         _ ->@@ -88,6 +104,12 @@  -- | -- /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@@ -98,7 +120,17 @@ 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 Monoid (Deque a) where   mempty =     Deque [] []@@ -111,4 +143,20 @@   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)