{-# LANGUAGE CPP #-}
module Deque.Strict.Defs where
import Deque.Prelude hiding (dropWhile, filter, head, init, last, null, reverse, tail, take, takeWhile)
import qualified Deque.Prelude as Prelude
import qualified StrictList
data Deque a = Deque !(StrictList.List a) !(StrictList.List a)
{-# INLINE fromConsAndSnocLists #-}
fromConsAndSnocLists :: [a] -> [a] -> Deque a
fromConsAndSnocLists :: forall a. [a] -> [a] -> Deque a
fromConsAndSnocLists [a]
consList [a]
snocList = forall a. List a -> List a -> Deque a
Deque (forall l. IsList l => [Item l] -> l
fromList [a]
consList) (forall l. IsList l => [Item l] -> l
fromList [a]
snocList)
{-# INLINE cons #-}
cons :: a -> Deque a -> Deque a
cons :: forall a. a -> Deque a -> Deque a
cons a
a (Deque List a
consList List a
snocList) = forall a. List a -> List a -> Deque a
Deque (forall a. a -> List a -> List a
StrictList.Cons a
a List a
consList) List a
snocList
{-# INLINE snoc #-}
snoc :: a -> Deque a -> Deque a
snoc :: forall a. a -> Deque a -> Deque a
snoc a
a (Deque List a
consList List a
snocList) = forall a. List a -> List a -> Deque a
Deque List a
consList (forall a. a -> List a -> List a
StrictList.Cons a
a List a
snocList)
{-# INLINE reverse #-}
reverse :: Deque a -> Deque a
reverse :: forall a. Deque a -> Deque a
reverse (Deque List a
consList List a
snocList) = forall a. List a -> List a -> Deque a
Deque List a
snocList List a
consList
{-# INLINE shiftLeft #-}
shiftLeft :: Deque a -> Deque a
shiftLeft :: forall a. Deque a -> Deque a
shiftLeft Deque a
deque = forall b a. b -> (a -> b) -> Maybe a -> b
maybe Deque a
deque (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a. a -> Deque a -> Deque a
snoc) (forall a. Deque a -> Maybe (a, Deque a)
uncons Deque a
deque)
{-# INLINE shiftRight #-}
shiftRight :: Deque a -> Deque a
shiftRight :: forall a. Deque a -> Deque a
shiftRight Deque a
deque = forall b a. b -> (a -> b) -> Maybe a -> b
maybe Deque a
deque (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a. a -> Deque a -> Deque a
cons) (forall a. Deque a -> Maybe (a, Deque a)
unsnoc Deque a
deque)
balanceLeft :: Deque a -> Deque a
balanceLeft :: forall a. Deque a -> Deque a
balanceLeft = forall a. HasCallStack => [Char] -> a
error [Char]
"TODO"
{-# INLINE filter #-}
filter :: (a -> Bool) -> Deque a -> Deque a
filter :: forall a. (a -> Bool) -> Deque a -> Deque a
filter a -> Bool
predicate (Deque List a
consList List a
snocList) =
let newConsList :: List a
newConsList =
forall a. List a -> List a -> List a
StrictList.prependReversed
(forall a. (a -> Bool) -> List a -> List a
StrictList.filterReversed a -> Bool
predicate List a
consList)
(forall a. (a -> Bool) -> List a -> List a
StrictList.filterReversed a -> Bool
predicate List a
snocList)
in forall a. List a -> List a -> Deque a
Deque List a
newConsList forall a. List a
StrictList.Nil
take :: Int -> Deque a -> Deque a
take :: forall a. Int -> Deque a -> Deque a
take Int
amount (Deque List a
consList List a
snocList) =
let newSnocList :: List a
newSnocList =
let buildFromConsList :: Int -> List a -> List a -> List a
buildFromConsList Int
amount !List a
list =
if Int
amount forall a. Ord a => a -> a -> Bool
> Int
0
then \case
StrictList.Cons a
head List a
tail -> Int -> List a -> List a -> List a
buildFromConsList (forall a. Enum a => a -> a
pred Int
amount) (forall a. a -> List a -> List a
StrictList.Cons a
head List a
list) List a
tail
List a
_ -> forall {t} {a}.
(Ord t, Num t, Enum t) =>
t -> List a -> List a -> List a
buildFromSnocList Int
amount List a
list (forall a. List a -> List a
StrictList.reverse List a
snocList)
else forall a b. a -> b -> a
const List a
list
buildFromSnocList :: t -> List a -> List a -> List a
buildFromSnocList t
amount !List a
list =
if t
amount forall a. Ord a => a -> a -> Bool
> t
0
then \case
StrictList.Cons a
head List a
tail -> t -> List a -> List a -> List a
buildFromSnocList (forall a. Enum a => a -> a
pred t
amount) (forall a. a -> List a -> List a
StrictList.Cons a
head List a
list) List a
tail
List a
_ -> List a
list
else forall a b. a -> b -> a
const List a
list
in Int -> List a -> List a -> List a
buildFromConsList Int
amount forall a. List a
StrictList.Nil List a
consList
in forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil List a
newSnocList
drop :: Int -> Deque a -> Deque a
drop :: forall a. Int -> Deque a -> Deque a
drop Int
amount (Deque List a
consList List a
snocList) =
let buildFromConsList :: Int -> List a -> Deque a
buildFromConsList Int
amount =
if Int
amount forall a. Ord a => a -> a -> Bool
> Int
0
then \case
StrictList.Cons a
_ List a
tail -> Int -> List a -> Deque a
buildFromConsList (forall a. Enum a => a -> a
pred Int
amount) List a
tail
List a
_ -> forall {t} {a}. (Ord t, Num t, Enum t) => t -> List a -> Deque a
buildFromSnocList Int
amount (forall a. List a -> List a
StrictList.reverse List a
snocList)
else \List a
tail -> forall a. List a -> List a -> Deque a
Deque List a
tail List a
snocList
buildFromSnocList :: t -> List a -> Deque a
buildFromSnocList t
amount =
if t
amount forall a. Ord a => a -> a -> Bool
> t
0
then \case
StrictList.Cons a
_ List a
tail -> t -> List a -> Deque a
buildFromSnocList (forall a. Enum a => a -> a
pred t
amount) List a
tail
List a
_ -> forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil forall a. List a
StrictList.Nil
else \List a
tail -> forall a. List a -> List a -> Deque a
Deque List a
tail forall a. List a
StrictList.Nil
in Int -> List a -> Deque a
buildFromConsList Int
amount List a
consList
{-# INLINE takeWhile #-}
takeWhile :: (a -> Bool) -> Deque a -> Deque a
takeWhile :: forall a. (a -> Bool) -> Deque a -> Deque a
takeWhile a -> Bool
predicate (Deque List a
consList List a
snocList) =
let newConsList :: List a
newConsList =
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr
( \a
a List a
nextState ->
if a -> Bool
predicate a
a
then forall a. a -> List a -> List a
StrictList.Cons a
a List a
nextState
else forall a. List a
StrictList.Nil
)
(forall a. (a -> Bool) -> List a -> List a
StrictList.takeWhileFromEnding a -> Bool
predicate List a
snocList)
List a
consList
in forall a. List a -> List a -> Deque a
Deque List a
newConsList forall a. List a
StrictList.Nil
{-# INLINE dropWhile #-}
dropWhile :: (a -> Bool) -> Deque a -> Deque a
dropWhile :: forall a. (a -> Bool) -> Deque a -> Deque a
dropWhile a -> Bool
predicate (Deque List a
consList List a
snocList) =
let newConsList :: List a
newConsList = forall a. (a -> Bool) -> List a -> List a
StrictList.dropWhile a -> Bool
predicate List a
consList
in case List a
newConsList of
List a
StrictList.Nil -> forall a. List a -> List a -> Deque a
Deque (forall a. (a -> Bool) -> List a -> List a
StrictList.dropWhileFromEnding a -> Bool
predicate List a
snocList) forall a. List a
StrictList.Nil
List a
_ -> forall a. List a -> List a -> Deque a
Deque List a
newConsList List a
snocList
span :: (a -> Bool) -> Deque a -> (Deque a, Deque a)
span :: forall a. (a -> Bool) -> Deque a -> (Deque a, Deque a)
span a -> Bool
predicate (Deque List a
consList List a
snocList) = case forall a. (a -> Bool) -> List a -> (List a, List a)
StrictList.spanReversed a -> Bool
predicate List a
consList of
(List a
consReversedPrefix, List a
consSuffix) ->
if forall (t :: * -> *) a. Foldable t => t a -> Bool
Prelude.null List a
consSuffix
then case forall a. (a -> Bool) -> List a -> (List a, List a)
StrictList.spanFromEnding a -> Bool
predicate List a
snocList of
(List a
snocPrefix, List a
snocSuffix) ->
let prefix :: Deque a
prefix = forall a. List a -> List a -> Deque a
Deque (forall a. List a -> List a -> List a
StrictList.prependReversed List a
consReversedPrefix List a
snocPrefix) forall a. List a
StrictList.Nil
suffix :: Deque a
suffix = forall a. List a -> List a -> Deque a
Deque List a
snocSuffix forall a. List a
StrictList.Nil
in (Deque a
prefix, Deque a
suffix)
else
let prefix :: Deque a
prefix = forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil List a
consReversedPrefix
suffix :: Deque a
suffix = forall a. List a -> List a -> Deque a
Deque List a
consSuffix List a
snocList
in (Deque a
prefix, Deque a
suffix)
{-# INLINE uncons #-}
uncons :: Deque a -> Maybe (a, Deque a)
uncons :: forall a. Deque a -> Maybe (a, Deque a)
uncons (Deque List a
consList List a
snocList) = case List a
consList of
StrictList.Cons a
head List a
tail -> forall a. a -> Maybe a
Just (a
head, forall a. List a -> List a -> Deque a
Deque List a
tail List a
snocList)
List a
_ -> case forall a. List a -> List a
StrictList.reverse List a
snocList of
StrictList.Cons a
head List a
tail -> forall a. a -> Maybe a
Just (a
head, forall a. List a -> List a -> Deque a
Deque List a
tail forall a. List a
StrictList.Nil)
List a
_ -> forall a. Maybe a
Nothing
{-# INLINE unsnoc #-}
unsnoc :: Deque a -> Maybe (a, Deque a)
unsnoc :: forall a. Deque a -> Maybe (a, Deque a)
unsnoc (Deque List a
consList List a
snocList) = case List a
snocList of
StrictList.Cons a
head List a
tail -> forall a. a -> Maybe a
Just (a
head, forall a. List a -> List a -> Deque a
Deque List a
consList List a
tail)
List a
_ -> case forall a. List a -> List a
StrictList.reverse List a
consList of
StrictList.Cons a
head List a
tail -> forall a. a -> Maybe a
Just (a
head, forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil List a
tail)
List a
_ -> forall a. Maybe a
Nothing
{-# INLINE null #-}
null :: Deque a -> Bool
null :: forall a. Deque a -> Bool
null = \case
Deque List a
StrictList.Nil List a
StrictList.Nil -> Bool
True
Deque a
_ -> Bool
False
{-# INLINE head #-}
head :: Deque a -> Maybe a
head :: forall a. Deque a -> Maybe a
head (Deque List a
consList List a
snocList) = case List a
consList of
StrictList.Cons a
head List a
_ -> forall a. a -> Maybe a
Just a
head
List a
_ -> forall a. List a -> Maybe a
StrictList.last List a
snocList
{-# INLINE last #-}
last :: Deque a -> Maybe a
last :: forall a. Deque a -> Maybe a
last (Deque List a
consList List a
snocList) = case List a
snocList of
StrictList.Cons a
head List a
_ -> forall a. a -> Maybe a
Just a
head
List a
_ -> forall a. List a -> Maybe a
StrictList.last List a
consList
{-# INLINE tail #-}
tail :: Deque a -> Deque a
tail :: forall a. Deque a -> Deque a
tail (Deque List a
consList List a
snocList) = case List a
consList of
StrictList.Cons a
_ List a
consListTail -> forall a. List a -> List a -> Deque a
Deque List a
consListTail List a
snocList
List a
_ -> forall a. List a -> List a -> Deque a
Deque (forall a. List a -> List a
StrictList.initReversed List a
snocList) forall a. List a
StrictList.Nil
{-# INLINE init #-}
init :: Deque a -> Deque a
init :: forall a. Deque a -> Deque a
init (Deque List a
consList List a
snocList) = case List a
snocList of
List a
StrictList.Nil -> forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil (forall a. List a -> List a
StrictList.initReversed List a
consList)
List a
_ -> forall a. List a -> List a -> Deque a
Deque List a
consList (forall a. List a -> List a
StrictList.tail List a
snocList)
instance (Eq a) => Eq (Deque a) where
== :: Deque a -> Deque a -> Bool
(==) Deque a
a Deque a
b = forall l. IsList l => l -> [Item l]
toList Deque a
a forall a. Eq a => a -> a -> Bool
== forall l. IsList l => l -> [Item l]
toList Deque a
b
instance (Show a) => Show (Deque a) where
show :: Deque a -> [Char]
show = forall a. Show a => a -> [Char]
show forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall l. IsList l => l -> [Item l]
toList
instance IsList (Deque a) where
type Item (Deque a) = a
fromList :: [Item (Deque a)] -> Deque a
fromList [Item (Deque a)]
list = forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil (forall a. [a] -> List a
StrictList.fromListReversed [Item (Deque a)]
list)
toList :: Deque a -> [Item (Deque a)]
toList (Deque List a
consList List a
snocList) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) (forall l. IsList l => l -> [Item l]
toList (forall a. List a -> List a
StrictList.reverse List a
snocList)) List a
consList
instance Semigroup (Deque a) where
<> :: Deque a -> Deque a -> Deque a
(<>) (Deque List a
consList1 List a
snocList1) (Deque List a
consList2 List a
snocList2) =
let consList :: List a
consList = List a
consList1
snocList :: List a
snocList = List a
snocList2 forall a. Semigroup a => a -> a -> a
<> forall a. List a -> List a -> List a
StrictList.prependReversed List a
consList2 List a
snocList1
in forall a. List a -> List a -> Deque a
Deque List a
consList List a
snocList
instance Monoid (Deque a) where
mempty :: Deque a
mempty = forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil forall a. List a
StrictList.Nil
mappend :: Deque a -> Deque a -> Deque a
mappend = forall a. Semigroup a => a -> a -> a
(<>)
deriving instance Functor Deque
instance Foldable Deque where
foldr :: forall a b. (a -> b -> b) -> b -> Deque a -> b
foldr a -> b -> b
step b
init (Deque List a
consList List a
snocList) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
step (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
step b
init (forall a. List a -> List a
StrictList.reverse List a
snocList)) List a
consList
foldl' :: forall b a. (b -> a -> b) -> b -> Deque a -> b
foldl' b -> a -> b
step b
init (Deque List a
consList List a
snocList) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
step (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
step b
init List a
consList) (forall a. List a -> List a
StrictList.reverse List a
snocList)
instance Traversable Deque where
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Deque a -> f (Deque b)
traverse a -> f b
f (Deque List a
cs List a
ss) =
(\List b
cs' List b
ss' -> forall a. List a -> List a -> Deque a
Deque List b
cs' (forall a. List a -> List a
StrictList.reverse List b
ss')) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f List a
cs forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f (forall a. List a -> List a
StrictList.reverse List a
ss)
instance Applicative Deque where
pure :: forall a. a -> Deque a
pure a
a = forall a. List a -> List a -> Deque a
Deque (forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a) forall a. List a
StrictList.Nil
<*> :: forall a b. Deque (a -> b) -> Deque a -> Deque b
(<*>) (Deque List (a -> b)
fnConsList List (a -> b)
fnSnocList) (Deque List a
argConsList List a
argSnocList) =
let snocList :: List b
snocList =
let fnStep :: List b -> (a -> b) -> List b
fnStep List b
resultSnocList a -> b
fn =
let argStep :: List b -> a -> List b
argStep List b
resultSnocList a
arg = forall a. a -> List a -> List a
StrictList.Cons (a -> b
fn a
arg) List b
resultSnocList
in forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> a -> List b
argStep (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> a -> List b
argStep List b
resultSnocList List a
argConsList) (forall a. List a -> List a
StrictList.reverse List a
argSnocList)
in forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> (a -> b) -> List b
fnStep (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> (a -> b) -> List b
fnStep forall a. List a
StrictList.Nil List (a -> b)
fnConsList) (forall a. List a -> List a
StrictList.reverse List (a -> b)
fnSnocList)
in forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil List b
snocList
instance Monad Deque where
return :: forall a. a -> Deque a
return = forall (f :: * -> *) a. Applicative f => a -> f a
pure
>>= :: forall a b. Deque a -> (a -> Deque b) -> Deque b
(>>=) (Deque List a
aConsList List a
aSnocList) a -> Deque b
k =
let snocList :: List b
snocList =
let aStep :: List b -> a -> List b
aStep List b
accBSnocList a
a = case a -> Deque b
k a
a of
Deque List b
bConsList List b
bSnocList -> forall a. List a -> List a -> List a
StrictList.prependReversed List b
bConsList (List b
bSnocList forall a. Semigroup a => a -> a -> a
<> List b
accBSnocList)
in forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> a -> List b
aStep (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> a -> List b
aStep forall a. List a
StrictList.Nil List a
aConsList) (forall a. List a -> List a
StrictList.reverse List a
aSnocList)
in forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil List b
snocList
#if !(MIN_VERSION_base(4,13,0))
fail = const mempty
#endif
instance Alternative Deque where
empty :: forall a. Deque a
empty = forall a. Monoid a => a
mempty
<|> :: forall a. Deque a -> Deque a -> Deque a
(<|>) = forall a. Monoid a => a -> a -> a
mappend
instance MonadPlus Deque where
mzero :: forall a. Deque a
mzero = forall (f :: * -> *) a. Alternative f => f a
empty
mplus :: forall a. Deque a -> Deque a -> Deque a
mplus = forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>)
instance MonadFail Deque where
fail :: forall a. [Char] -> Deque a
fail = forall a b. a -> b -> a
const forall a. Monoid a => a
mempty
deriving instance Generic (Deque a)
deriving instance Generic1 Deque
instance (Hashable a) => Hashable (Deque a)
instance (NFData a) => NFData (Deque a)
instance NFData1 Deque