{-# 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 qualified Data.List as List
import Deque.Prelude hiding (dropWhile, filter, head, init, last, null, reverse, tail, take, takeWhile)

-- |
-- 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 :: forall a. [a] -> [a] -> Deque a
fromConsAndSnocLists [a]
consList [a]
snocList = 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 :: forall a. (a -> Bool) -> Deque a -> Deque a
filter a -> Bool
predicate (Deque [a]
consList [a]
snocList) = forall a. [a] -> [a] -> Deque a
Deque (forall a. (a -> Bool) -> [a] -> [a]
List.filter a -> Bool
predicate [a]
consList) (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 :: forall a. 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 forall a. Ord a => a -> a -> Bool
> Int
0
                then \case
                  a
head : [a]
tail -> a
head forall a. a -> [a] -> [a]
: Int -> [a] -> [a]
buildFromConsList (forall a. Enum a => a -> a
pred Int
amount) [a]
tail
                  [a]
_ -> forall {t} {a}. (Ord t, Num t, Enum t) => t -> [a] -> [a]
buildFromSnocList Int
amount (forall a. [a] -> [a]
List.reverse [a]
snocList)
                else forall a b. a -> b -> a
const []
            buildFromSnocList :: t -> [a] -> [a]
buildFromSnocList t
amount =
              if t
amount forall a. Ord a => a -> a -> Bool
> t
0
                then \case
                  a
head : [a]
tail -> a
head forall a. a -> [a] -> [a]
: t -> [a] -> [a]
buildFromSnocList (forall a. Enum a => a -> a
pred t
amount) [a]
tail
                  [a]
_ -> []
                else forall a b. a -> b -> a
const []
         in Int -> [a] -> [a]
buildFromConsList Int
amount [a]
consList
   in 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 :: forall a. 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 forall a. Ord a => a -> a -> Bool
> Int
0
          then \case
            a
_ : [a]
tail -> Int -> [a] -> Deque a
buildFromConsList (forall a. Enum a => a -> a
pred Int
amount) [a]
tail
            [a]
_ -> forall {t} {a}. (Ord t, Num t, Enum t) => t -> [a] -> Deque a
buildFromSnocList Int
amount (forall a. [a] -> [a]
List.reverse [a]
snocList)
          else \[a]
tail -> forall a. [a] -> [a] -> Deque a
Deque [a]
tail [a]
snocList
      buildFromSnocList :: t -> [a] -> Deque a
buildFromSnocList t
amount =
        if t
amount forall a. Ord a => a -> a -> Bool
> t
0
          then \case
            a
_ : [a]
tail -> t -> [a] -> Deque a
buildFromSnocList (forall a. Enum a => a -> a
pred t
amount) [a]
tail
            [a]
_ -> forall a. [a] -> [a] -> Deque a
Deque [] []
          else \[a]
tail -> 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 :: forall a. (a -> Bool) -> Deque a -> Deque a
takeWhile a -> Bool
predicate (Deque [a]
consList [a]
snocList) =
  let newConsList :: [a]
newConsList =
        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 forall a. a -> [a] -> [a]
: [a]
nextState
                else []
          )
          (forall a. (a -> Bool) -> [a] -> [a]
List.takeWhile a -> Bool
predicate (forall a. [a] -> [a]
List.reverse [a]
snocList))
          [a]
consList
   in 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 :: forall a. (a -> Bool) -> Deque a -> Deque a
dropWhile a -> Bool
predicate (Deque [a]
consList [a]
snocList) =
  let newConsList :: [a]
newConsList = forall a. (a -> Bool) -> [a] -> [a]
List.dropWhile a -> Bool
predicate [a]
consList
   in case [a]
newConsList of
        [] -> forall a. [a] -> [a] -> Deque a
Deque (forall a. (a -> Bool) -> [a] -> [a]
List.dropWhile a -> Bool
predicate (forall a. [a] -> [a]
List.reverse [a]
snocList)) []
        [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 :: forall a. (a -> Bool) -> Deque a -> (Deque a, Deque a)
span a -> Bool
predicate (Deque [a]
consList [a]
snocList) = case forall a. (a -> Bool) -> [a] -> ([a], [a])
List.span a -> Bool
predicate [a]
consList of
  ([a]
consPrefix, [a]
consSuffix) ->
    if forall (t :: * -> *) a. Foldable t => t a -> Bool
List.null [a]
consSuffix
      then case forall a. (a -> Bool) -> [a] -> ([a], [a])
List.span a -> Bool
predicate (forall a. [a] -> [a]
List.reverse [a]
snocList) of
        ([a]
snocPrefix, [a]
snocSuffix) ->
          let prefix :: Deque a
prefix = forall a. [a] -> [a] -> Deque a
Deque ([a]
consPrefix forall a. Semigroup a => a -> a -> a
<> [a]
snocPrefix) []
              suffix :: Deque a
suffix = forall a. [a] -> [a] -> Deque a
Deque [a]
snocSuffix []
           in (Deque a
prefix, Deque a
suffix)
      else
        let prefix :: Deque a
prefix = forall a. [a] -> [a] -> Deque a
Deque [a]
consPrefix []
            suffix :: Deque a
suffix = 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 :: 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)

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

-- |
-- \(\mathcal{O}(1)\).
-- Add element in the beginning.
cons :: a -> Deque a -> Deque a
cons :: forall a. a -> Deque a -> Deque a
cons a
a (Deque [a]
consList [a]
snocList) = forall a. [a] -> [a] -> Deque a
Deque (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 :: forall a. a -> Deque a -> Deque a
snoc a
a (Deque [a]
consList [a]
snocList) = forall a. [a] -> [a] -> Deque a
Deque [a]
consList (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 :: forall a. Deque a -> Maybe (a, Deque a)
uncons (Deque [a]
consList [a]
snocList) = case [a]
consList of
  a
head : [a]
tail -> forall a. a -> Maybe a
Just (a
head, forall a. [a] -> [a] -> Deque a
Deque [a]
tail [a]
snocList)
  [a]
_ -> case forall a. [a] -> [a]
List.reverse [a]
snocList of
    a
head : [a]
tail -> forall a. a -> Maybe a
Just (a
head, forall a. [a] -> [a] -> Deque a
Deque [a]
tail [])
    [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 :: forall a. Deque a -> Maybe (a, Deque a)
unsnoc (Deque [a]
consList [a]
snocList) = case [a]
snocList of
  a
head : [a]
tail -> forall a. a -> Maybe a
Just (a
head, forall a. [a] -> [a] -> Deque a
Deque [a]
consList [a]
tail)
  [a]
_ -> case forall a. [a] -> [a]
List.reverse [a]
consList of
    a
head : [a]
tail -> forall a. a -> Maybe a
Just (a
head, forall a. [a] -> [a] -> Deque a
Deque [] [a]
tail)
    [a]
_ -> forall a. Maybe a
Nothing

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

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

-- |
-- \(\mathcal{O}(1)\).
-- Check whether deque is empty.
null :: Deque a -> Bool
null :: forall a. Deque a -> Bool
null (Deque [a]
consList [a]
snocList) = forall (t :: * -> *) a. Foldable t => t a -> Bool
List.null [a]
snocList Bool -> Bool -> 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 :: forall a. Deque a -> Maybe a
head = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> a
fst forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. 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 :: forall a. Deque a -> Deque a
tail = forall a. a -> Maybe a -> a
fromMaybe forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> b
snd forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. 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 :: forall a. Deque a -> Deque a
init = forall a. a -> Maybe a -> a
fromMaybe forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall {k} (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> b
snd forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. 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 :: forall a. Deque a -> Maybe a
last = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> a
fst forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. 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 = 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 -> String
show = forall a. Show a => a -> String
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 Semigroup (Deque a) where
  <> :: Deque a -> Deque a -> Deque a
(<>) = forall a. Deque a -> Deque a -> Deque a
prepend

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

instance Foldable Deque where
  foldr :: forall a b. (a -> b -> b) -> b -> Deque a -> b
foldr a -> b -> b
step b
init (Deque [a]
consList [a]
snocList) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
step (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> b
step) b
init [a]
snocList) [a]
consList
  foldl' :: forall b a. (b -> a -> b) -> b -> Deque a -> b
foldl' b -> a -> b
step b
init (Deque [a]
consList [a]
snocList) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' (forall a b c. (a -> b -> c) -> b -> a -> c
flip b -> a -> b
step) (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 :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Deque a -> f (Deque b)
traverse a -> f b
f (Deque [a]
cs [a]
ss) =
    (\[b]
cs' [b]
ss' -> forall a. [a] -> [a] -> Deque a
Deque [b]
cs' (forall a. [a] -> [a]
List.reverse [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 [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. [a] -> [a]
List.reverse [a]
ss)

deriving instance Functor Deque

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

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 [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 forall a. Semigroup a => a -> a -> a
<> forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip (:)) [b]
accBConsList [b]
bSnocList
           in forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> [b] -> [b]
aStep (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> [b] -> [b]
aStep [] (forall a. [a] -> [a]
List.reverse [a]
aSnocList)) [a]
aConsList
     in 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 :: 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. String -> Deque a
fail = forall a b. a -> b -> a
const 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 = forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a. [a] -> [a] -> Deque a
Deque []
  toList :: Deque a -> [Item (Deque a)]
toList (Deque [a]
consList [a]
snocList) = [a]
consList forall a. Semigroup 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