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

    -- |
    -- /O(n)/.
    -- Construct from cons and snoc lists.
    fromConsAndSnocLists :: [a] -> [a] -> Deque a
    fromConsAndSnocLists :: [a] -> [a] -> Deque a
    fromConsAndSnocLists consList :: [a]
    consList snocList :: [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)

    -- |
    -- /O(1)/.
    -- Add element in the beginning.
    cons :: a -> Deque a -> Deque a
    cons :: a -> Deque a -> Deque a
    cons a :: a
    a (Deque consList :: List a
    consList snocList :: 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

    -- |
    -- /O(1)/.
    -- Add element in the ending.
    snoc :: a -> Deque a -> Deque a
    snoc :: a -> Deque a -> Deque a
    snoc a :: a
    a (Deque consList :: List a
    consList snocList :: 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)

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

    -- |
    -- /O(1)/, occasionally /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 :: 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)

    -- |
    -- /O(1)/, occasionally /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 :: 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)

    -- |
    -- /O(n)/.
    -- Leave only the elements satisfying the predicate.
    filter :: (a -> Bool) -> Deque a -> Deque a
    filter :: (a -> Bool) -> Deque a -> Deque a
    filter predicate :: a -> Bool
    predicate (Deque consList :: List a
    consList snocList :: 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

    -- |
    -- /O(n)/.
    -- Leave only the specified amount of first elements.
    take :: Int -> Deque a -> Deque a
    take :: Int -> Deque a -> Deque a
    take amount :: Int
    amount (Deque consList :: List a
    consList snocList :: List a
    snocList) = let
      newSnocList :: List a
    newSnocList = let
        buildFromConsList :: Int -> List a -> List a -> List a
    buildFromConsList amount :: Int
    amount !List a
    list = if Int
    amount Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > 0
          then \ case
            StrictList.Cons head :: a
    head tail :: 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
            _ -> 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 amount :: t
    amount !List a
    list = if t
    amount t -> t -> Bool
    forall a. Ord a => a -> a -> Bool
    > 0
          then \ case
            StrictList.Cons head :: a
    head tail :: 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
          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

    -- |
    -- /O(n)/.
    -- Drop the specified amount of first elements.
    drop :: Int -> Deque a -> Deque a
    drop :: Int -> Deque a -> Deque a
    drop amount :: Int
    amount (Deque consList :: List a
    consList snocList :: List a
    snocList) = let
      buildFromConsList :: Int -> List a -> Deque a
    buildFromConsList amount :: Int
    amount = if Int
    amount Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > 0
        then \ case
          StrictList.Cons _ tail :: List a
    tail -> Int -> List a -> Deque a
    buildFromConsList (Int -> Int
    forall a. Enum a => a -> a
    pred Int
    amount) List a
    tail
          _ -> 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 \ tail :: 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 amount :: t
    amount = if t
    amount t -> t -> Bool
    forall a. Ord a => a -> a -> Bool
    > 0
        then \ case
          StrictList.Cons _ tail :: 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 -> 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 \ tail :: 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

    -- |
    -- /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 predicate :: a -> Bool
    predicate (Deque consList :: List a
    consList snocList :: 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
    a nextState :: 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

    -- |
    -- /O(n)/.
    -- Drop the first elements satisfying the predicate.
    dropWhile :: (a -> Bool) -> Deque a -> Deque a
    dropWhile :: (a -> Bool) -> Deque a -> Deque a
    dropWhile predicate :: a -> Bool
    predicate (Deque consList :: List a
    consList snocList :: 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
        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 -> Deque a
    forall a. List a -> List a -> Deque a
    Deque List a
    newConsList List a
    snocList

    -- |
    -- /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 predicate :: a -> Bool
    predicate (Deque consList :: List a
    consList snocList :: 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
      (consReversedPrefix :: List a
    consReversedPrefix, consSuffix :: 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
          (snocPrefix :: List a
    snocPrefix, snocSuffix :: 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)

    -- |
    -- /O(1)/, occasionally /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 consList :: List a
    consList snocList :: List a
    snocList) = case List a
    consList of
      StrictList.Cons head :: a
    head tail :: 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)
      _ -> case List a -> List a
    forall a. List a -> List a
    StrictList.reverse List a
    snocList of
        StrictList.Cons head :: a
    head tail :: 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)
        _ -> Maybe (a, Deque a)
    forall a. Maybe a
    Nothing

    -- |
    -- /O(1)/, occasionally /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 consList :: List a
    consList snocList :: List a
    snocList) = case List a
    snocList of
      StrictList.Cons head :: a
    head tail :: 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)
      _ -> case List a -> List a
    forall a. List a -> List a
    StrictList.reverse List a
    consList of
        StrictList.Cons head :: a
    head tail :: 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)
        _ -> Maybe (a, Deque a)
    forall a. Maybe a
    Nothing

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

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

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

    -- |
    -- /O(1)/, occasionally /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 consList :: List a
    consList snocList :: List a
    snocList) = case List a
    consList of
      StrictList.Nil -> 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
      _ -> 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.tail List a
    consList) List a
    snocList

    -- |
    -- /O(1)/, occasionally /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 consList :: List a
    consList snocList :: List a
    snocList) = case List a
    snocList of
      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 -> 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
    (==) a :: Deque a
    a b :: 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 IsList (Deque a) where
      type Item (Deque a) = a
      fromList :: [Item (Deque a)] -> Deque a
    fromList list :: [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 consList :: List a
    consList snocList :: 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 consList1 :: List a
    consList1 snocList1 :: List a
    snocList1) (Deque consList2 :: List a
    consList2 snocList2 :: 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 step :: a -> b -> b
    step init :: b
    init (Deque consList :: List a
    consList snocList :: 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' step :: b -> a -> b
    step init :: b
    init (Deque consList :: List a
    consList snocList :: 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 f :: a -> f b
    f (Deque cs :: List a
    cs ss :: List a
    ss) =
        (\cs' :: List b
    cs' ss' :: 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
    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 fnConsList :: List (a -> b)
    fnConsList fnSnocList :: List (a -> b)
    fnSnocList) (Deque argConsList :: List a
    argConsList argSnocList :: List a
    argSnocList) = let
        snocList :: List b
    snocList = let
          fnStep :: List b -> (a -> b) -> List b
    fnStep resultSnocList :: List b
    resultSnocList fn :: a -> b
    fn = let
            argStep :: List b -> a -> List b
    argStep resultSnocList :: List b
    resultSnocList arg :: 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 aConsList :: List a
    aConsList aSnocList :: List a
    aSnocList) k :: a -> Deque b
    k = let
        snocList :: List b
    snocList = let
          aStep :: List b -> a -> List b
    aStep accBSnocList :: List b
    accBSnocList a :: a
    a = case a -> Deque b
    k a
    a of
            Deque bConsList :: List b
    bConsList bSnocList :: 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 :: String -> Deque a
    fail = Deque a -> String -> 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)