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 StrictList
data Deque a = Deque {-# UNPACK #-} !(StrictList.List a) {-# UNPACK #-} !(StrictList.List a)
fromConsAndSnocLists :: [a] -> [a] -> Deque a
fromConsAndSnocLists consList snocList = Deque (fromList snocList) (fromList consList)
cons :: a -> Deque a -> Deque a
cons a (Deque snocList consList) = Deque snocList (StrictList.Cons a consList)
snoc :: a -> Deque a -> Deque a
snoc a (Deque snocList consList) = Deque (StrictList.Cons a snocList) consList
reverse :: Deque a -> Deque a
reverse (Deque snocList consList) = Deque consList snocList
shiftLeft :: Deque a -> Deque a
shiftLeft deque = maybe deque (uncurry snoc) (uncons deque)
shiftRight :: Deque a -> Deque a
shiftRight deque = maybe deque (uncurry cons) (unsnoc deque)
filter :: (a -> Bool) -> Deque a -> Deque a
filter predicate (Deque snocList consList) = let
newConsList = StrictList.prependReversed
(StrictList.filterReversed predicate consList)
(StrictList.filterReversed predicate snocList)
in Deque StrictList.Nil newConsList
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
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
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
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
null :: Deque a -> Bool
null = \ case
Deque StrictList.Nil StrictList.Nil -> True
_ -> False
head :: Deque a -> Maybe a
head (Deque snocList consList) = case consList of
StrictList.Cons head _ -> Just head
_ -> StrictList.last snocList
last :: Deque a -> Maybe a
last (Deque snocList consList) = case snocList of
StrictList.Cons head _ -> Just head
_ -> StrictList.last consList
tail :: Deque a -> Deque a
tail (Deque snocList consList) = case consList of
StrictList.Nil -> Deque StrictList.Nil (StrictList.initReversed snocList)
_ -> Deque snocList (StrictList.tail consList)
init :: Deque a -> Deque a
init (Deque snocList consList) = case snocList of
StrictList.Nil -> Deque (StrictList.initReversed consList) StrictList.Nil
_ -> Deque (StrictList.tail snocList) consList
instance Eq a => Eq (Deque a) where
(==) a b = toList a == toList b
instance Show a => Show (Deque a) where
show = showString "fromList " . show . toList
instance IsList (Deque a) where
type Item (Deque a) = a
fromList list = Deque (StrictList.fromListReversed list) StrictList.Nil
toList (Deque snocList consList) = foldr (:) (toList (StrictList.reverse snocList)) consList
instance Semigroup (Deque a) where
(<>) (Deque snocList1 consList1) (Deque snocList2 consList2) = let
snocList3 = snocList2
consList3 = consList1 <> StrictList.prependReversed snocList1 consList2
in Deque snocList3 consList3
instance Monoid (Deque a) where
mempty = Deque StrictList.Nil StrictList.Nil
mappend = (<>)
deriving instance Functor Deque
instance Foldable Deque where
foldr step init (Deque snocList consList) = foldr step (foldr step init (StrictList.reverse snocList)) consList
foldl' step init (Deque snocList consList) = foldl' step (foldl' step init consList) (StrictList.reverse snocList)
instance Traversable Deque where
traverse f (Deque ss cs) =
(\cs' ss' -> Deque (StrictList.reverse ss') cs') <$> traverse f cs <*> traverse f (StrictList.reverse ss)
instance Applicative Deque where
pure a = Deque StrictList.Nil (pure a)
fs <*> as = fromList (toList fs <*> toList as)
instance Monad Deque where
return = pure
m >>= f = fromList (toList m >>= toList . f)
fail = const mempty
instance Alternative Deque where
empty = mempty
(<|>) = mappend
instance MonadPlus Deque where
mzero = empty
mplus = (<|>)
instance MonadFail Deque where
fail = const mempty