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

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

-- |
-- Lazy double-ended queue (aka Dequeue or Deque) based on head-tail linked list.
data Deque a = Deque ![a] ![a]

-- |
-- \(\mathcal{O}(1)\).
-- Construct from cons and snoc lists.
fromConsAndSnocLists :: [a] -> [a] -> Deque a
fromConsAndSnocLists :: [a] -> [a] -> Deque a
fromConsAndSnocLists [a]
consList [a]
snocList = [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
consList [a]
snocList

-- |
-- \(\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 [a]
consList [a]
snocList) = [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
List.filter a -> Bool
predicate [a]
consList) ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
List.filter a -> Bool
predicate [a]
snocList)

-- |
-- \(\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 [a]
consList [a]
snocList) = let
  newConsList :: [a]
newConsList = let
    buildFromConsList :: Int -> [a] -> [a]
buildFromConsList Int
amount = if Int
amount Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0
      then \ case
        a
head : [a]
tail -> a
head a -> [a] -> [a]
forall a. a -> [a] -> [a]
: Int -> [a] -> [a]
buildFromConsList (Int -> Int
forall a. Enum a => a -> a
pred Int
amount) [a]
tail
        [a]
_ -> Int -> [a] -> [a]
forall t a. (Ord t, Num t, Enum t) => t -> [a] -> [a]
buildFromSnocList Int
amount ([a] -> [a]
forall a. [a] -> [a]
List.reverse [a]
snocList)
      else [a] -> [a] -> [a]
forall a b. a -> b -> a
const []
    buildFromSnocList :: t -> [a] -> [a]
buildFromSnocList t
amount = if t
amount t -> t -> Bool
forall a. Ord a => a -> a -> Bool
> t
0
      then \ case
        a
head : [a]
tail -> a
head a -> [a] -> [a]
forall a. a -> [a] -> [a]
: t -> [a] -> [a]
buildFromSnocList (t -> t
forall a. Enum a => a -> a
pred t
amount) [a]
tail
        [a]
_ -> []
      else [a] -> [a] -> [a]
forall a b. a -> b -> a
const []
    in Int -> [a] -> [a]
buildFromConsList Int
amount [a]
consList
  in [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
newConsList []

-- |
-- \(\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 [a]
consList [a]
snocList) = let
  buildFromConsList :: Int -> [a] -> Deque a
buildFromConsList Int
amount = if Int
amount Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0
    then \ case
      a
_ : [a]
tail -> Int -> [a] -> Deque a
buildFromConsList (Int -> Int
forall a. Enum a => a -> a
pred Int
amount) [a]
tail
      [a]
_ -> Int -> [a] -> Deque a
forall t a. (Ord t, Num t, Enum t) => t -> [a] -> Deque a
buildFromSnocList Int
amount ([a] -> [a]
forall a. [a] -> [a]
List.reverse [a]
snocList)
    else \ [a]
tail -> [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
tail [a]
snocList
  buildFromSnocList :: t -> [a] -> Deque a
buildFromSnocList t
amount = if t
amount t -> t -> Bool
forall a. Ord a => a -> a -> Bool
> t
0
    then \ case
      a
_ : [a]
tail -> t -> [a] -> Deque a
buildFromSnocList (t -> t
forall a. Enum a => a -> a
pred t
amount) [a]
tail
      [a]
_ -> [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [] []
    else \ [a]
tail -> [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
tail []
  in Int -> [a] -> Deque a
buildFromConsList Int
amount [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 [a]
consList [a]
snocList) = let
  newConsList :: [a]
newConsList = (a -> [a] -> [a]) -> [a] -> [a] -> [a]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
List.foldr
    (\ a
a [a]
nextState -> if a -> Bool
predicate a
a
      then a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
nextState
      else [])
    ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
List.takeWhile a -> Bool
predicate ([a] -> [a]
forall a. [a] -> [a]
List.reverse [a]
snocList))
    [a]
consList
  in [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
newConsList []

-- |
-- \(\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 [a]
consList [a]
snocList) = let
  newConsList :: [a]
newConsList = (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
List.dropWhile a -> Bool
predicate [a]
consList
  in case [a]
newConsList of
    [] -> [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
List.dropWhile a -> Bool
predicate ([a] -> [a]
forall a. [a] -> [a]
List.reverse [a]
snocList)) []
    [a]
_ -> [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
newConsList [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 [a]
consList [a]
snocList) = case (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.span a -> Bool
predicate [a]
consList of
  ([a]
consPrefix, [a]
consSuffix) -> if [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
List.null [a]
consSuffix
    then case (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.span a -> Bool
predicate ([a] -> [a]
forall a. [a] -> [a]
List.reverse [a]
snocList) of
      ([a]
snocPrefix, [a]
snocSuffix) -> let
        prefix :: Deque a
prefix = [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque ([a]
consPrefix [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> [a]
snocPrefix) []
        suffix :: Deque a
suffix = [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
snocSuffix []
        in (Deque a
prefix, Deque a
suffix)
    else let
      prefix :: Deque a
prefix = [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
consPrefix []
      suffix :: Deque a
suffix = [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
consSuffix [a]
snocList
      in (Deque a
prefix, Deque a
suffix)

-- |
-- \(\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)

-- |
-- \(\mathcal{O}(1)\).
-- Add element in the beginning.
cons :: a -> Deque a -> Deque a
cons :: a -> Deque a -> Deque a
cons a
a (Deque [a]
consList [a]
snocList) = [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque (a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
consList) [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 [a]
consList [a]
snocList) = [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
consList (a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
snocList)

-- |
-- \(\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 [a]
consList [a]
snocList) = case [a]
consList of
  a
head : [a]
tail -> (a, Deque a) -> Maybe (a, Deque a)
forall a. a -> Maybe a
Just (a
head, [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
tail [a]
snocList)
  [a]
_ -> case [a] -> [a]
forall a. [a] -> [a]
List.reverse [a]
snocList of
    a
head : [a]
tail -> (a, Deque a) -> Maybe (a, Deque a)
forall a. a -> Maybe a
Just (a
head, [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
tail [])
    [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 [a]
consList [a]
snocList) = case [a]
snocList of
  a
head : [a]
tail -> (a, Deque a) -> Maybe (a, Deque a)
forall a. a -> Maybe a
Just (a
head, [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
consList [a]
tail)
  [a]
_ -> case [a] -> [a]
forall a. [a] -> [a]
List.reverse [a]
consList of
    a
head : [a]
tail -> (a, Deque a) -> Maybe (a, Deque a)
forall a. a -> Maybe a
Just (a
head, [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [] [a]
tail)
    [a]
_ -> Maybe (a, Deque a)
forall a. Maybe a
Nothing

-- |
-- \(\mathcal{O}(n)\).
prepend :: Deque a -> Deque a -> Deque a
prepend :: Deque a -> Deque a -> Deque a
prepend (Deque [a]
consList1 [a]
snocList1) (Deque [a]
consList2 [a]
snocList2) = let
  consList :: [a]
consList = [a]
consList1
  snocList :: [a]
snocList = [a]
snocList2 [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ ([a] -> a -> [a]) -> [a] -> [a] -> [a]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((a -> [a] -> [a]) -> [a] -> a -> [a]
forall a b c. (a -> b -> c) -> b -> a -> c
flip (:)) [a]
snocList1 [a]
consList2
  in [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
consList [a]
snocList

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

-- |
-- \(\mathcal{O}(1)\). 
-- Check whether deque is empty.
null :: Deque a -> Bool
null :: Deque a -> Bool
null (Deque [a]
consList [a]
snocList) = [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
List.null [a]
snocList Bool -> Bool -> Bool
&& [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
List.null [a]
consList

-- |
-- \(\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 = ((a, Deque a) -> a) -> Maybe (a, Deque a) -> Maybe a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, Deque a) -> a
forall a b. (a, b) -> a
fst (Maybe (a, Deque a) -> Maybe a)
-> (Deque a -> Maybe (a, Deque a)) -> Deque a -> Maybe a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Deque a -> Maybe (a, Deque a)
forall a. Deque a -> Maybe (a, Deque a)
uncons

-- |
-- \(\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 a -> Maybe (Deque a) -> Deque a
forall a. a -> Maybe a -> a
fromMaybe (Deque a -> Maybe (Deque a) -> Deque a)
-> (Deque a -> Deque a) -> Deque a -> Maybe (Deque a) -> Deque a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Deque a -> Deque a
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id (Deque a -> Maybe (Deque a) -> Deque a)
-> (Deque a -> Maybe (Deque a)) -> Deque a -> Deque a
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> ((a, Deque a) -> Deque a) -> Maybe (a, Deque a) -> Maybe (Deque a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, Deque a) -> Deque a
forall a b. (a, b) -> b
snd (Maybe (a, Deque a) -> Maybe (Deque a))
-> (Deque a -> Maybe (a, Deque a)) -> Deque a -> Maybe (Deque a)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Deque a -> Maybe (a, Deque a)
forall a. Deque a -> Maybe (a, Deque a)
uncons

-- |
-- \(\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 a -> Maybe (Deque a) -> Deque a
forall a. a -> Maybe a -> a
fromMaybe (Deque a -> Maybe (Deque a) -> Deque a)
-> (Deque a -> Deque a) -> Deque a -> Maybe (Deque a) -> Deque a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Deque a -> Deque a
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id (Deque a -> Maybe (Deque a) -> Deque a)
-> (Deque a -> Maybe (Deque a)) -> Deque a -> Deque a
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> ((a, Deque a) -> Deque a) -> Maybe (a, Deque a) -> Maybe (Deque a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, Deque a) -> Deque a
forall a b. (a, b) -> b
snd (Maybe (a, Deque a) -> Maybe (Deque a))
-> (Deque a -> Maybe (a, Deque a)) -> Deque a -> Maybe (Deque a)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Deque a -> Maybe (a, Deque a)
forall a. Deque a -> Maybe (a, Deque a)
unsnoc

-- |
-- \(\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 = ((a, Deque a) -> a) -> Maybe (a, Deque a) -> Maybe a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, Deque a) -> a
forall a b. (a, b) -> a
fst (Maybe (a, Deque a) -> Maybe a)
-> (Deque a -> Maybe (a, Deque a)) -> Deque a -> Maybe a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Deque a -> Maybe (a, Deque a)
forall a. Deque a -> Maybe (a, Deque a)
unsnoc


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 -> String
show = [a] -> String
forall a. Show a => a -> String
show ([a] -> String) -> (Deque a -> [a]) -> Deque a -> String
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 Semigroup (Deque a) where
  <> :: Deque a -> Deque a -> Deque a
(<>) = Deque a -> Deque a -> Deque a
forall a. Deque a -> Deque a -> Deque a
prepend

instance Monoid (Deque a) where
  mempty :: Deque a
mempty =
    [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [] []
  mappend :: Deque a -> Deque a -> Deque a
mappend =
    Deque a -> Deque a -> Deque a
forall a. Semigroup a => a -> a -> a
(<>)

instance Foldable Deque where
  foldr :: (a -> b -> b) -> b -> Deque a -> b
foldr a -> b -> b
step b
init (Deque [a]
consList [a]
snocList) = (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
step ((b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((a -> b -> b) -> b -> a -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> b
step) b
init [a]
snocList) [a]
consList
  foldl' :: (b -> a -> b) -> b -> Deque a -> b
foldl' b -> a -> b
step b
init (Deque [a]
consList [a]
snocList) = (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' ((b -> a -> b) -> a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip b -> a -> b
step) ((b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
step b
init [a]
consList) [a]
snocList

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

deriving instance Functor Deque

instance Applicative Deque where
  pure :: a -> Deque a
pure a
a = [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [] [a
a]
  <*> :: Deque (a -> b) -> Deque a -> Deque b
(<*>) (Deque [a -> b]
fnConsList [a -> b]
fnSnocList) (Deque [a]
argConsList [a]
argSnocList) = let
    consList :: [b]
consList = let
      fnStep :: (a -> b) -> [b] -> [b]
fnStep a -> b
fn [b]
resultConsList = let
        argStep :: a -> [b] -> [b]
argStep a
arg = (:) (a -> b
fn a
arg)
        in (a -> [b] -> [b]) -> [b] -> [a] -> [b]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> [b] -> [b]
argStep ((a -> [b] -> [b]) -> [b] -> [a] -> [b]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> [b] -> [b]
argStep [b]
resultConsList ([a] -> [a]
forall a. [a] -> [a]
List.reverse [a]
argSnocList)) [a]
argConsList
      in ((a -> b) -> [b] -> [b]) -> [b] -> [a -> b] -> [b]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (a -> b) -> [b] -> [b]
fnStep (((a -> b) -> [b] -> [b]) -> [b] -> [a -> b] -> [b]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (a -> b) -> [b] -> [b]
fnStep [] ([a -> b] -> [a -> b]
forall a. [a] -> [a]
List.reverse [a -> b]
fnSnocList)) [a -> b]
fnConsList 
    in [b] -> [b] -> Deque b
forall a. [a] -> [a] -> Deque a
Deque [b]
consList []

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 [a]
aConsList [a]
aSnocList) a -> Deque b
k = let
    consList :: [b]
consList = let
      aStep :: a -> [b] -> [b]
aStep a
a [b]
accBConsList = case a -> Deque b
k a
a of
        Deque [b]
bConsList [b]
bSnocList -> [b]
bConsList [b] -> [b] -> [b]
forall a. Semigroup a => a -> a -> a
<> ([b] -> b -> [b]) -> [b] -> [b] -> [b]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((b -> [b] -> [b]) -> [b] -> b -> [b]
forall a b c. (a -> b -> c) -> b -> a -> c
flip (:)) [b]
accBConsList [b]
bSnocList
      in (a -> [b] -> [b]) -> [b] -> [a] -> [b]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> [b] -> [b]
aStep ((a -> [b] -> [b]) -> [b] -> [a] -> [b]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> [b] -> [b]
aStep [] ([a] -> [a]
forall a. [a] -> [a]
List.reverse [a]
aSnocList)) [a]
aConsList
    in [b] -> [b] -> Deque b
forall a. [a] -> [a] -> Deque a
Deque [b]
consList []
#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 :: String -> Deque a
fail = Deque a -> String -> Deque a
forall a b. a -> b -> a
const Deque a
forall a. Monoid a => a
mempty

-- |
-- \(\mathcal{O}(1)\).
instance IsList (Deque a) where
  type Item (Deque a) = a
  fromList :: [Item (Deque a)] -> Deque a
fromList = ([a] -> [a] -> Deque a) -> [a] -> [a] -> Deque a
forall a b c. (a -> b -> c) -> b -> a -> c
flip [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque []
  toList :: Deque a -> [Item (Deque a)]
toList (Deque [a]
consList [a]
snocList) = [a]
consList [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> [a] -> [a]
forall a. [a] -> [a]
List.reverse [a]
snocList

deriving instance Generic (Deque a)
deriving instance Generic1 Deque

instance Hashable a => Hashable (Deque a)

instance NFData a => NFData (Deque a)
instance NFData1 Deque