{-# 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

import Control.Monad (fail)
import Deque.Prelude hiding (tail, init, last, head, null, dropWhile, takeWhile, reverse, filter, take)
import qualified StrictList
import qualified Deque.Prelude as Prelude

-- |
-- Strict double-ended queue (aka Dequeue or Deque) based on head-tail linked list.
data Deque a = Deque !(StrictList.List a) !(StrictList.List a)

-- |
-- \(\mathcal{O}(n)\).
-- Construct from cons and snoc lists.
fromConsAndSnocLists :: [a] -> [a] -> Deque a
fromConsAndSnocLists :: [a] -> [a] -> Deque a
fromConsAndSnocLists [a]
consList [a]
snocList = List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque ([Item (List a)] -> List a
forall l. IsList l => [Item l] -> l
fromList [a]
[Item (List a)]
consList) ([Item (List a)] -> List a
forall l. IsList l => [Item l] -> l
fromList [a]
[Item (List a)]
snocList)

-- |
-- \(\mathcal{O}(1)\).
-- Add element in the beginning.
cons :: a -> Deque a -> Deque a
cons :: a -> Deque a -> Deque a
cons a
a (Deque List a
consList List a
snocList) = List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque (a -> List a -> List a
forall a. a -> List a -> List a
StrictList.Cons a
a List a
consList) List a
snocList

-- |
-- \(\mathcal{O}(1)\).
-- Add element in the ending.
snoc :: a -> Deque a -> Deque a
snoc :: a -> Deque a -> Deque a
snoc a
a (Deque List a
consList List a
snocList) = List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
consList (a -> List a -> List a
forall a. a -> List a -> List a
StrictList.Cons a
a List a
snocList)

-- |
-- \(\mathcal{O}(1)\).
-- Reverse the deque.
reverse :: Deque a -> Deque a
reverse :: Deque a -> Deque a
reverse (Deque List a
consList List a
snocList) = List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
snocList List a
consList

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Move the first element to the end.
--
-- @
-- λ toList . shiftLeft $ fromList [1,2,3]
-- [2,3,1]
-- @
shiftLeft :: Deque a -> Deque a
shiftLeft :: Deque a -> Deque a
shiftLeft Deque a
deque = Deque a
-> ((a, Deque a) -> Deque a) -> Maybe (a, Deque a) -> Deque a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Deque a
deque ((a -> Deque a -> Deque a) -> (a, Deque a) -> Deque a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> Deque a -> Deque a
forall a. a -> Deque a -> Deque a
snoc) (Deque a -> Maybe (a, Deque a)
forall a. Deque a -> Maybe (a, Deque a)
uncons Deque a
deque)

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Move the last element to the beginning.
--
-- @
-- λ toList . shiftRight $ fromList [1,2,3]
-- [3,1,2]
-- @
shiftRight :: Deque a -> Deque a
shiftRight :: Deque a -> Deque a
shiftRight Deque a
deque = Deque a
-> ((a, Deque a) -> Deque a) -> Maybe (a, Deque a) -> Deque a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Deque a
deque ((a -> Deque a -> Deque a) -> (a, Deque a) -> Deque a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> Deque a -> Deque a
forall a. a -> Deque a -> Deque a
cons) (Deque a -> Maybe (a, Deque a)
forall a. Deque a -> Maybe (a, Deque a)
unsnoc Deque a
deque)

balanceLeft :: Deque a -> Deque a
balanceLeft :: Deque a -> Deque a
balanceLeft = [Char] -> Deque a -> Deque a
forall a. HasCallStack => [Char] -> a
error [Char]
"TODO"

-- |
-- \(\mathcal{O}(n)\).
-- Leave only the elements satisfying the predicate.
filter :: (a -> Bool) -> Deque a -> Deque a
filter :: (a -> Bool) -> Deque a -> Deque a
filter a -> Bool
predicate (Deque List a
consList List a
snocList) = let
  newConsList :: List a
newConsList = List a -> List a -> List a
forall a. List a -> List a -> List a
StrictList.prependReversed
    ((a -> Bool) -> List a -> List a
forall a. (a -> Bool) -> List a -> List a
StrictList.filterReversed a -> Bool
predicate List a
consList)
    ((a -> Bool) -> List a -> List a
forall a. (a -> Bool) -> List a -> List a
StrictList.filterReversed a -> Bool
predicate List a
snocList)
  in List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
newConsList List a
forall a. List a
StrictList.Nil

-- |
-- \(\mathcal{O}(n)\).
-- Leave only the specified amount of first elements.
take :: Int -> Deque a -> Deque a
take :: 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 Int -> Int -> Bool
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 (Int -> Int
forall a. Enum a => a -> a
pred Int
amount) (a -> List a -> List a
forall a. a -> List a -> List a
StrictList.Cons a
head List a
list) List a
tail
        List a
_ -> Int -> List a -> List a -> List a
forall t a.
(Ord t, Num t, Enum t) =>
t -> List a -> List a -> List a
buildFromSnocList Int
amount List a
list (List a -> List a
forall a. List a -> List a
StrictList.reverse List a
snocList)
      else List a -> List a -> List a
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 t -> t -> Bool
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 (t -> t
forall a. Enum a => a -> a
pred t
amount) (a -> List a -> List a
forall a. a -> List a -> List a
StrictList.Cons a
head List a
list) List a
tail
        List a
_ -> List a
list
      else List a -> List a -> List a
forall a b. a -> b -> a
const List a
list
    in Int -> List a -> List a -> List a
buildFromConsList Int
amount List a
forall a. List a
StrictList.Nil List a
consList
  in List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
forall a. List a
StrictList.Nil List a
newSnocList

-- |
-- \(\mathcal{O}(n)\).
-- Drop the specified amount of first elements.
drop :: Int -> Deque a -> Deque a
drop :: 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0
    then \ case
      StrictList.Cons a
_ List a
tail -> Int -> List a -> Deque a
buildFromConsList (Int -> Int
forall a. Enum a => a -> a
pred Int
amount) List a
tail
      List a
_ -> Int -> List a -> Deque a
forall t a. (Ord t, Num t, Enum t) => t -> List a -> Deque a
buildFromSnocList Int
amount (List a -> List a
forall a. List a -> List a
StrictList.reverse List a
snocList)
    else \ List a
tail -> List a -> List a -> Deque a
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 t -> t -> Bool
forall a. Ord a => a -> a -> Bool
> t
0
    then \ case
      StrictList.Cons a
_ List a
tail -> t -> List a -> Deque a
buildFromSnocList (t -> t
forall a. Enum a => a -> a
pred t
amount) List a
tail
      List a
_ -> List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
forall a. List a
StrictList.Nil List a
forall a. List a
StrictList.Nil
    else \ List a
tail -> List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
tail List a
forall a. List a
StrictList.Nil
  in Int -> List a -> Deque a
buildFromConsList Int
amount List a
consList

-- |
-- \(\mathcal{O}(n)\).
-- Leave only the first elements satisfying the predicate.
takeWhile :: (a -> Bool) -> Deque a -> Deque a
takeWhile :: (a -> Bool) -> Deque a -> Deque a
takeWhile a -> Bool
predicate (Deque List a
consList List a
snocList) = let
  newConsList :: List a
newConsList = (a -> List a -> List a) -> List a -> List a -> List a
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 a -> List a -> List a
forall a. a -> List a -> List a
StrictList.Cons a
a List a
nextState
      else List a
forall a. List a
StrictList.Nil)
    ((a -> Bool) -> List a -> List a
forall a. (a -> Bool) -> List a -> List a
StrictList.takeWhileFromEnding a -> Bool
predicate List a
snocList)
    List a
consList
  in List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
newConsList List a
forall a. List a
StrictList.Nil

-- |
-- \(\mathcal{O}(n)\).
-- Drop the first elements satisfying the predicate.
dropWhile :: (a -> Bool) -> Deque a -> Deque a
dropWhile :: (a -> Bool) -> Deque a -> Deque a
dropWhile a -> Bool
predicate (Deque List a
consList List a
snocList) = let
  newConsList :: List a
newConsList = (a -> Bool) -> List a -> List a
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 -> List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque ((a -> Bool) -> List a -> List a
forall a. (a -> Bool) -> List a -> List a
StrictList.dropWhileFromEnding a -> Bool
predicate List a
snocList) List a
forall a. List a
StrictList.Nil
    List a
_ -> List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
newConsList List a
snocList

-- |
-- \(\mathcal{O}(n)\).
-- Perform `takeWhile` and `dropWhile` in a single operation.
span :: (a -> Bool) -> Deque a -> (Deque a, Deque a)
span :: (a -> Bool) -> Deque a -> (Deque a, Deque a)
span a -> Bool
predicate (Deque List a
consList List a
snocList) = case (a -> Bool) -> List a -> (List a, List a)
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 List a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Prelude.null List a
consSuffix
    then case (a -> Bool) -> List a -> (List a, List a)
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 = List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque (List a -> List a -> List a
forall a. List a -> List a -> List a
StrictList.prependReversed List a
consReversedPrefix List a
snocPrefix) List a
forall a. List a
StrictList.Nil
        suffix :: Deque a
suffix = List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
snocSuffix List a
forall a. List a
StrictList.Nil
        in (Deque a
prefix, Deque a
suffix)
    else let
      prefix :: Deque a
prefix = List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
forall a. List a
StrictList.Nil List a
consReversedPrefix
      suffix :: Deque a
suffix = List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
consSuffix List a
snocList
      in (Deque a
prefix, Deque a
suffix)

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the first element and deque without it if it's not empty.
uncons :: Deque a -> Maybe (a, Deque a)
uncons :: 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 -> (a, Deque a) -> Maybe (a, Deque a)
forall a. a -> Maybe a
Just (a
head, List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
tail List a
snocList)
  List a
_ -> case List a -> List a
forall a. List a -> List a
StrictList.reverse List a
snocList of
    StrictList.Cons a
head List a
tail -> (a, Deque a) -> Maybe (a, Deque a)
forall a. a -> Maybe a
Just (a
head, List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
tail List a
forall a. List a
StrictList.Nil)
    List a
_ -> Maybe (a, Deque a)
forall a. Maybe a
Nothing

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the last element and deque without it if it's not empty.
unsnoc :: Deque a -> Maybe (a, Deque a)
unsnoc :: 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 -> (a, Deque a) -> Maybe (a, Deque a)
forall a. a -> Maybe a
Just (a
head, List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
consList List a
tail)
  List a
_ -> case List a -> List a
forall a. List a -> List a
StrictList.reverse List a
consList of
    StrictList.Cons a
head List a
tail -> (a, Deque a) -> Maybe (a, Deque a)
forall a. a -> Maybe a
Just (a
head, List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
forall a. List a
StrictList.Nil List a
tail)
    List a
_ -> Maybe (a, Deque a)
forall a. Maybe a
Nothing

-- |
-- \(\mathcal{O}(1)\). 
-- Check whether deque is empty.
null :: Deque a -> Bool
null :: Deque a -> Bool
null = \ case
  Deque List a
StrictList.Nil List a
StrictList.Nil -> Bool
True
  Deque a
_ -> Bool
False

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the first element if deque is not empty.
head :: Deque a -> Maybe a
head :: Deque a -> Maybe a
head (Deque List a
consList List a
snocList) = case List a
consList of
  StrictList.Cons a
head List a
_ -> a -> Maybe a
forall a. a -> Maybe a
Just a
head
  List a
_ -> List a -> Maybe a
forall a. List a -> Maybe a
StrictList.last List a
snocList

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the last element if deque is not empty.
last :: Deque a -> Maybe a
last :: Deque a -> Maybe a
last (Deque List a
consList List a
snocList) = case List a
snocList of
  StrictList.Cons a
head List a
_ -> a -> Maybe a
forall a. a -> Maybe a
Just a
head
  List a
_ -> List a -> Maybe a
forall a. List a -> Maybe a
StrictList.last List a
consList

-- |
-- \(\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 :: Deque a -> Deque a
tail (Deque List a
consList List a
snocList) = case List a
consList of
  StrictList.Cons a
_ List a
consListTail -> List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
consListTail List a
snocList
  List a
_ -> List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque (List a -> List a
forall a. List a -> List a
StrictList.initReversed List a
snocList) List a
forall a. List a
StrictList.Nil

-- |
-- \(\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 :: Deque a -> Deque a
init (Deque List a
consList List a
snocList) = case List a
snocList of
  List a
StrictList.Nil -> List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
forall a. List a
StrictList.Nil (List a -> List a
forall a. List a -> List a
StrictList.initReversed List a
consList)
  List a
_ -> List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
consList (List a -> List a
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 = Deque a -> [Item (Deque a)]
forall l. IsList l => l -> [Item l]
toList Deque a
a [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== Deque a -> [Item (Deque a)]
forall l. IsList l => l -> [Item l]
toList Deque a
b

instance Show a => Show (Deque a) where
  show :: Deque a -> [Char]
show = [a] -> [Char]
forall a. Show a => a -> [Char]
show ([a] -> [Char]) -> (Deque a -> [a]) -> Deque a -> [Char]
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Deque a -> [a]
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 = List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
forall a. List a
StrictList.Nil ([a] -> List a
forall a. [a] -> List a
StrictList.fromListReversed [a]
[Item (Deque a)]
list)
  toList :: Deque a -> [Item (Deque a)]
toList (Deque List a
consList List a
snocList) = (a -> [a] -> [a]) -> [a] -> List a -> [a]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) (List a -> [Item (List a)]
forall l. IsList l => l -> [Item l]
toList (List a -> List a
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 List a -> List a -> List a
forall a. Semigroup a => a -> a -> a
<> List a -> List a -> List a
forall a. List a -> List a -> List a
StrictList.prependReversed List a
consList2 List a
snocList1
    in List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
consList List a
snocList

instance Monoid (Deque a) where
  mempty :: Deque a
mempty = List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque List a
forall a. List a
StrictList.Nil List a
forall a. List a
StrictList.Nil
  mappend :: Deque a -> Deque a -> Deque a
mappend = Deque a -> Deque a -> Deque a
forall a. Semigroup a => a -> a -> a
(<>)

deriving instance Functor Deque

instance Foldable Deque where
  foldr :: (a -> b -> b) -> b -> Deque a -> b
foldr a -> b -> b
step b
init (Deque List a
consList List a
snocList) = (a -> b -> b) -> b -> List a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
step ((a -> b -> b) -> b -> List a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
step b
init (List a -> List a
forall a. List a -> List a
StrictList.reverse List a
snocList)) List a
consList
  foldl' :: (b -> a -> b) -> b -> Deque a -> b
foldl' b -> a -> b
step b
init (Deque List a
consList List a
snocList) = (b -> a -> b) -> b -> List a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
step ((b -> a -> b) -> b -> List a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
step b
init List a
consList) (List a -> List a
forall a. List a -> List a
StrictList.reverse List a
snocList)

instance Traversable Deque where
  traverse :: (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' -> List b -> List b -> Deque b
forall a. List a -> List a -> Deque a
Deque List b
cs' (List b -> List b
forall a. List a -> List a
StrictList.reverse List b
ss')) (List b -> List b -> Deque b)
-> f (List b) -> f (List b -> Deque b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> List a -> f (List 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 f (List b -> Deque b) -> f (List b) -> f (Deque b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (a -> f b) -> List a -> f (List 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 -> List a
forall a. List a -> List a
StrictList.reverse List a
ss)

instance Applicative Deque where
  pure :: a -> Deque a
pure a
a = List a -> List a -> Deque a
forall a. List a -> List a -> Deque a
Deque (a -> List a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a) List a
forall a. List a
StrictList.Nil
  <*> :: 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 = b -> List b -> List b
forall a. a -> List a -> List a
StrictList.Cons (a -> b
fn a
arg) List b
resultSnocList
        in (List b -> a -> List b) -> List b -> List a -> List b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> a -> List b
argStep ((List b -> a -> List b) -> List b -> List a -> List b
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) (List a -> List a
forall a. List a -> List a
StrictList.reverse List a
argSnocList)
      in (List b -> (a -> b) -> List b) -> List b -> List (a -> b) -> List b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> (a -> b) -> List b
fnStep ((List b -> (a -> b) -> List b) -> List b -> List (a -> b) -> List b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> (a -> b) -> List b
fnStep List b
forall a. List a
StrictList.Nil List (a -> b)
fnConsList) (List (a -> b) -> List (a -> b)
forall a. List a -> List a
StrictList.reverse List (a -> b)
fnSnocList)
    in List b -> List b -> Deque b
forall a. List a -> List a -> Deque a
Deque List b
forall a. List a
StrictList.Nil List b
snocList

instance Monad Deque where
  return :: a -> Deque a
return = a -> Deque a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
  >>= :: 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 -> List b -> List b -> List b
forall a. List a -> List a -> List a
StrictList.prependReversed List b
bConsList (List b
bSnocList List b -> List b -> List b
forall a. Semigroup a => a -> a -> a
<> List b
accBSnocList)
      in (List b -> a -> List b) -> List b -> List a -> List b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> a -> List b
aStep ((List b -> a -> List b) -> List b -> List a -> List b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> a -> List b
aStep List b
forall a. List a
StrictList.Nil List a
aConsList) (List a -> List a
forall a. List a -> List a
StrictList.reverse List a
aSnocList)
    in List b -> List b -> Deque b
forall a. List a -> List a -> Deque a
Deque List b
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 :: Deque a
empty = Deque a
forall a. Monoid a => a
mempty
  <|> :: Deque a -> Deque a -> Deque a
(<|>) = Deque a -> Deque a -> Deque a
forall a. Monoid a => a -> a -> a
mappend

instance MonadPlus Deque where
  mzero :: Deque a
mzero = Deque a
forall (f :: * -> *) a. Alternative f => f a
empty
  mplus :: Deque a -> Deque a -> Deque a
mplus = Deque a -> Deque a -> Deque a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>)

instance MonadFail Deque where
  fail :: [Char] -> Deque a
fail = Deque a -> [Char] -> Deque a
forall a b. a -> b -> a
const Deque a
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