    {-# 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 = [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 :: forall a. (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 :: 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 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 :: 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 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 :: forall a. (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 a b. (a -> b -> b) -> b -> [a] -> b
    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 :: forall a. (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 :: forall a. (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 a. [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 :: 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]
    -- @
    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)

    -- |
    -- \(\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) = [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 :: forall a. 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 :: forall a. 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 :: forall a. 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 :: 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 [a] -> [a] -> [a]
    forall a. [a] -> [a] -> [a]
    ++ ([a] -> a -> [a]) -> [a] -> [a] -> [a]
    forall b a. (b -> a -> b) -> b -> [a] -> b
    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 :: forall a. 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 :: forall a. Deque a -> Bool
    null (Deque [a]
    consList [a]
    snocList) = [a] -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    List.null [a]
    snocList Bool -> Bool -> Bool
    && [a] -> Bool
    forall a. [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 :: forall a. Deque a -> Maybe a
    head = ((a, Deque a) -> a) -> Maybe (a, Deque a) -> Maybe a
    forall a b. (a -> b) -> Maybe a -> Maybe b
    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 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 -> 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 :: forall a. 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 a. a -> 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 a b. (Deque a -> a -> b) -> (Deque a -> a) -> Deque a -> b
    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 a b. (a -> b) -> Maybe a -> Maybe b
    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 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 -> 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 :: forall a. 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 a. a -> 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 a b. (Deque a -> a -> b) -> (Deque a -> a) -> Deque a -> b
    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 a b. (a -> b) -> Maybe a -> Maybe b
    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 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 -> 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 :: forall a. Deque a -> Maybe a
    last = ((a, Deque a) -> a) -> Maybe (a, Deque a) -> Maybe a
    forall a b. (a -> b) -> Maybe a -> Maybe b
    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 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 -> 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 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 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 :: forall a b. (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 a b. (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 b a. (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' :: forall b a. (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 a b. (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 b a. (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 :: 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' -> [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)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> [a] -> f [b]
    traverse a -> f b
    f [a]
    cs f ([b] -> Deque b) -> f [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) -> [a] -> f [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) -> [a] -> f [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 :: forall a. a -> Deque a
    pure a
    a = [a] -> [a] -> Deque 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 (a -> [b] -> [b]) -> [b] -> [a] -> [b]
    forall a b. (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 a b. (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 a b. (a -> b -> b) -> b -> [a] -> 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 a b. (a -> b -> b) -> b -> [a] -> 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 :: 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 [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 b a. (b -> a -> b) -> b -> [a] -> 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 a b. (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 a b. (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 :: 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. 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