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

    -- |
    -- 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.
    {-# INLINE fromConsAndSnocLists #-}
    fromConsAndSnocLists :: [a] -> [a] -> Deque a
    fromConsAndSnocLists :: forall a. [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.
    {-# 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) = 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.
    {-# 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) = 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.
    {-# INLINE reverse #-}
    reverse :: Deque a -> Deque a
    reverse :: forall a. 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]
    -- @
    {-# INLINE shiftLeft #-}
    shiftLeft :: Deque a -> Deque a
    shiftLeft :: forall a. 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]
    -- @
    {-# INLINE shiftRight #-}
    shiftRight :: Deque a -> Deque a
    shiftRight :: forall a. 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 :: forall a. 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.
    {-# 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 =
            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 :: 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 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 :: 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 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.
    {-# 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 =
            (a -> List a -> List a) -> List a -> List a -> List a
    forall a b. (a -> b -> b) -> b -> List a -> b
    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.
    {-# 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 = (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 :: forall a. (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 a. 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.
    {-# 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 -> (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.
    {-# 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 -> (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.
    {-# 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

    -- |
    -- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
    -- Get the first element if deque is not empty.
    {-# 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
    _ -> 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.
    {-# 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
    _ -> 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.
    {-# 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 -> 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.
    {-# 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 -> 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 b c a. (b -> c) -> (a -> b) -> a -> c
    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]
    Deque a -> [Item (Deque 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 a b. (a -> b -> b) -> b -> List a -> b
    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 :: forall a b. (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 a b. (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 a b. (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' :: forall b a. (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 b a. (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 b a. (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 :: 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' -> 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)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> List a -> f (List b)
    traverse a -> f b
    f List a
    cs f (List b -> Deque b) -> f (List b) -> f (Deque b)
    forall a b. f (a -> b) -> f a -> f 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)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> List a -> f (List 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 :: forall a. 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 a. a -> List a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure a
    a) List 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 = 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 b a. (b -> a -> b) -> b -> List a -> 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 b a. (b -> a -> b) -> b -> List a -> 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 b a. (b -> a -> b) -> b -> List a -> 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 b a. (b -> a -> b) -> b -> List a -> 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 :: forall a. a -> Deque a
    return = a -> Deque a
    forall a. a -> Deque a
    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 -> 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 b a. (b -> a -> b) -> b -> List a -> 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 b a. (b -> a -> b) -> b -> List a -> 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 :: forall a. Deque a
    empty = Deque a
    forall a. Monoid a => a
    mempty
      <|> :: forall a. 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 :: forall a. Deque a
    mzero = Deque a
    forall a. Deque a
    forall (f :: * -> *) a. Alternative f => f a
    empty
      mplus :: forall a. Deque a -> Deque a -> Deque a
    mplus = Deque a -> Deque a -> Deque a
    forall a. Deque a -> Deque a -> Deque a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    (<|>)

    instance MonadFail Deque where
      fail :: forall a. [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