    {- ORMOLU_DISABLE -}
    -- Options passed to GHC
    {-# OPTIONS_GHC -O2 #-}
    -- Options passed to Haddock
    {-# OPTIONS_HADDOCK hide #-}

    -----------------------------------------------------------------------------

    {-# LANGUAGE CPP #-}

    {-

    We use __GLASGOW_HASKELL__ everywhere, so, rather than check if it's defined in
    multiple places, we assert an error here if it is not. Since the rest of the
    package depends on this module ('Data.DList.Internal'), we don't perform the
    same check everywhere else.

    -}
    #if !defined(__GLASGOW_HASKELL__)
    #error "Your compiler is not GHC. Let us know if dlist can be made to work on it."
    #endif

    -- For the IsList and IsString instances
    {-# LANGUAGE TypeFamilies #-}

    -- CPP: GHC >= 7.8 for pattern synonyms, Safe Haskell, view patterns
    #if __GLASGOW_HASKELL__ >= 708
    {- ORMOLU_ENABLE -}
    {-# LANGUAGE PatternSynonyms #-}
    {-

    The 'Data.DList.Internal' module exports 'UnsafeDList' and 'unsafeApplyDList',
    which allow breaking the invariant of the 'DList' newtype. Therefore, we
    explicitly mark 'Data.DList.Internal' as unsafe.

    -}
    {-# LANGUAGE Unsafe #-}
    {-# LANGUAGE ViewPatterns #-}
    {- ORMOLU_DISABLE -}
    #endif

    -----------------------------------------------------------------------------

    {-|

    Module: Data.DList.Internal
    Copyright: © 2006-2009 Don Stewart, 2013-2020 Sean Leather
    License: BSD-3-Clause

    Maintainer: sean.leather@gmail.com
    Stability: stable

    This module includes everything related to 'DList' and is not exposed to users
    of the @dlist@ package.

    -}
    {- ORMOLU_ENABLE -}

    module Data.DList.Internal where

    -----------------------------------------------------------------------------

    import qualified Control.Applicative as Applicative
    import Control.DeepSeq (NFData (..))
    import qualified Control.Monad as Monad
    -- CPP: base >= 4.9 for MonadFail
    -- CPP: base >= 4.13 for MonadFail exported from Control.Monad
    #if MIN_VERSION_base(4,9,0) && !MIN_VERSION_base(4,13,0)
    import qualified Control.Monad.Fail as Monad
    #endif
    import qualified Data.Foldable as Foldable
    import Data.Function (on)
    import qualified Data.List as List
    import qualified Data.Monoid as Monoid
    -- CPP: base >= 4.9 for Semigroup
    #if MIN_VERSION_base(4,9,0)
    import qualified Data.Semigroup as Semigroup
    #endif
    import Data.String (IsString (..))
    import qualified Data.Traversable as Traversable
    -- CPP: GHC >= 7.8 for IsList
    #if __GLASGOW_HASKELL__ >= 708
    import qualified GHC.Exts as Exts
    #endif
    import qualified Text.Read as Read
    import Prelude hiding (concat, foldr, head, map, replicate, tail)

    -----------------------------------------------------------------------------

    {- ORMOLU_DISABLE -}
    {-|

    A difference list is an abstraction representing a list that
    supports&#x00A0;\(\mathcal{O}\)(@1@) 'append' and 'snoc' operations, making it
    useful for replacing frequent applications of '++' such as logging and pretty
    printing (esp. if those uses of '++' are left-nested).

    -}
    {- ORMOLU_ENABLE -}

    newtype DList a = UnsafeDList {forall a. DList a -> [a] -> [a]
    unsafeApplyDList :: [a] -> [a]}

    {- ORMOLU_DISABLE -}
    {-|

    __@fromList xs@__ is a 'DList' representing the list __@xs@__.

    @fromList@ obeys the laws:

    @
    'toList' . __fromList__ = 'id'
    __fromList__ . 'toList' = 'id'
    @

    This function is implemented with '++'. Repeated uses of @fromList@ are just as
    inefficient as repeated uses of '++'. If you find yourself doing some form of
    the following (possibly indirectly), you may not be taking advantage of the
    'DList' representation and library:

    @
    __fromList__ . f . 'toList'
    @

    More likely, you will convert from a list, perform some operation on the
    'DList', and convert back to a list:

    @
    'toList' . g . __fromList__
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE fromList #-}
    fromList :: [a] -> DList a
    fromList :: forall a. [a] -> DList a
    fromList = ([a] -> [a]) -> DList a
    forall a. ([a] -> [a]) -> DList a
    UnsafeDList (([a] -> [a]) -> DList a) -> ([a] -> [a] -> [a]) -> [a] -> DList a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [a] -> [a] -> [a]
    forall a. [a] -> [a] -> [a]
    (++)

    {- ORMOLU_DISABLE -}
    {-|

    __@toList xs@__ is the list represented by __@xs@__.

    @toList@ obeys the laws:

    @
    __toList__ . 'fromList' = 'id'
    'fromList' . __toList__ = 'id'
    @

    Evaluating @toList xs@ may “collapse” the chain of function composition
    underlying many 'DList' functions ('append' in particular) used to construct
    @xs@. This may affect any efficiency you achieved due to laziness in the
    construction.

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE toList #-}
    toList :: DList a -> [a]
    toList :: forall a. DList a -> [a]
    toList = (([a] -> [a]) -> [a] -> [a]
    forall a b. (a -> b) -> a -> b
    $ []) (([a] -> [a]) -> [a]) -> (DList a -> [a] -> [a]) -> DList a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a] -> [a]
    forall a. DList a -> [a] -> [a]
    unsafeApplyDList

    -- CPP: GHC >= 7.8 for pattern synonyms
    #if __GLASGOW_HASKELL__ >= 708

    -- CPP: GHC >= 7.10 for pattern synonym signatures

    {- ORMOLU_DISABLE -}
    {-|

    A unidirectional pattern synonym for 'empty'. This is implemented with 'toList'.

    -}
    {- ORMOLU_ENABLE -}

    #if __GLASGOW_HASKELL__ >= 710
    pattern Nil :: DList a
    #endif
    pattern $mNil :: forall {r} {a}. DList a -> ((# #) -> r) -> ((# #) -> r) -> r
    Nil <- (toList -> [])

    {- ORMOLU_DISABLE -}
    {-|

    A unidirectional pattern synonym for 'cons'. This is implemented with 'toList'.

    -}
    {- ORMOLU_ENABLE -}

    #if __GLASGOW_HASKELL__ >= 710
    pattern Cons :: a -> [a] -> DList a
    #endif
    pattern $mCons :: forall {r} {a}. DList a -> (a -> [a] -> r) -> ((# #) -> r) -> r
    Cons x xs <- (toList -> x : xs)

    #endif

    {- ORMOLU_DISABLE -}
    {-|

    __@apply xs ys@__ is the list represented by the __@xs@__ after appending
    __@ys@__ to it.

    \(\mathcal{O}\)(@1@).

    @apply@ obeys the law:

    @
    __apply__ xs ys = 'toList' xs '++' ys
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE apply #-}
    apply :: DList a -> [a] -> [a]
    apply :: forall a. DList a -> [a] -> [a]
    apply = DList a -> [a] -> [a]
    forall a. DList a -> [a] -> [a]
    unsafeApplyDList

    {- ORMOLU_DISABLE -}
    {-|

    __@empty@__ is a 'DList' with no elements.

    @empty@ obeys the law:

    @
    'toList' __empty__ = []
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE empty #-}
    empty :: DList a
    empty :: forall a. DList a
    empty = ([a] -> [a]) -> DList a
    forall a. ([a] -> [a]) -> DList a
    UnsafeDList [a] -> [a]
    forall a. a -> a
    id

    {- ORMOLU_DISABLE -}
    {-|

    __@singleton x@__ is a 'DList' with the single element __@x@__.

    @singleton@ obeys the law:

    @
    'toList' (__singleton__ x) = [x]
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE singleton #-}
    singleton :: a -> DList a
    singleton :: forall a. a -> DList a
    singleton = ([a] -> [a]) -> DList a
    forall a. ([a] -> [a]) -> DList a
    UnsafeDList (([a] -> [a]) -> DList a) -> (a -> [a] -> [a]) -> a -> DList a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (:)

    {- ORMOLU_DISABLE -}
    {-|

    __@cons x xs@__ is a 'DList' with the 'head' __@x@__ and the 'tail' __@xs@__.

    \(\mathcal{O}\)(@1@).

    @cons@ obeys the law:

    @
    'toList' (__cons__ x xs) = x : 'toList' xs
    @

    -}
    {- ORMOLU_ENABLE -}

    infixr 9 `cons`

    {-# INLINE cons #-}
    cons :: a -> DList a -> DList a
    cons :: forall a. a -> DList a -> DList a
    cons a
    x DList a
    xs = ([a] -> [a]) -> DList a
    forall a. ([a] -> [a]) -> DList a
    UnsafeDList (([a] -> [a]) -> DList a) -> ([a] -> [a]) -> DList a
    forall a b. (a -> b) -> a -> b
    $ (a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :) ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a] -> [a]
    forall a. DList a -> [a] -> [a]
    unsafeApplyDList DList a
    xs

    infixl 9 `snoc`

    {- ORMOLU_DISABLE -}
    {-|

    __@snoc xs x@__ is a 'DList' with the initial 'DList' __@xs@__ and the last
    element __@x@__.

    \(\mathcal{O}\)(@1@).

    @snoc@ obeys the law:

    @
    'toList' (__snoc__ xs x) = 'toList' xs '++' [x]
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE snoc #-}
    snoc :: DList a -> a -> DList a
    snoc :: forall a. DList a -> a -> DList a
    snoc DList a
    xs a
    x = ([a] -> [a]) -> DList a
    forall a. ([a] -> [a]) -> DList a
    UnsafeDList (([a] -> [a]) -> DList a) -> ([a] -> [a]) -> DList a
    forall a b. (a -> b) -> a -> b
    $ DList a -> [a] -> [a]
    forall a. DList a -> [a] -> [a]
    unsafeApplyDList DList a
    xs ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :)

    {- ORMOLU_DISABLE -}
    {-|

    __@append xs ys@__ is a 'DList' obtained from the concatenation of the elements
    of __@xs@__ and __@ys@__.

    \(\mathcal{O}\)(@1@).

    @append@ obeys the law:

    @
    'toList' (__append__ xs ys) = 'toList' xs '++' 'toList' ys
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE append #-}
    append :: DList a -> DList a -> DList a
    append :: forall a. DList a -> DList a -> DList a
    append DList a
    xs DList a
    ys = ([a] -> [a]) -> DList a
    forall a. ([a] -> [a]) -> DList a
    UnsafeDList (([a] -> [a]) -> DList a) -> ([a] -> [a]) -> DList a
    forall a b. (a -> b) -> a -> b
    $ DList a -> [a] -> [a]
    forall a. DList a -> [a] -> [a]
    unsafeApplyDList DList a
    xs ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a] -> [a]
    forall a. DList a -> [a] -> [a]
    unsafeApplyDList DList a
    ys

    {- ORMOLU_DISABLE -}
    {-|

    __@concat xss@__ is a 'DList' representing the concatenation of all 'DList's in
    the list __@xss@__.

    \(\mathcal{O}\)(@'length' xss@).

    @concat@ obeys the law:

    @
    'toList' (__concat__ xss) = 'List.concat' ('List.map' 'toList' xss)
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE concat #-}
    concat :: [DList a] -> DList a
    concat :: forall a. [DList a] -> DList a
    concat = (DList a -> DList a -> DList a) -> DList a -> [DList a] -> DList 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 DList a -> DList a -> DList a
    forall a. DList a -> DList a -> DList a
    append DList a
    forall a. DList a
    empty

    {- ORMOLU_DISABLE -}
    {-|

    __@replicate n x@__ is a 'DList' of length __@n@__ with __@x@__ as the value of
    every element.

    \(\mathcal{O}\)(@n@).

    @replicate@ obeys the law:

    @
    'toList' (__replicate__ n x) = 'List.replicate' n x
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE replicate #-}
    replicate :: Int -> a -> DList a
    replicate :: forall a. Int -> a -> DList a
    replicate Int
    n a
    x = ([a] -> [a]) -> DList a
    forall a. ([a] -> [a]) -> DList a
    UnsafeDList (([a] -> [a]) -> DList a) -> ([a] -> [a]) -> DList a
    forall a b. (a -> b) -> a -> b
    $ \[a]
    xs ->
      let go :: Int -> [a]
    go Int
    m
            | Int
    m Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 = [a]
    xs
            | Bool
    otherwise = a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : Int -> [a]
    go (Int
    m Int -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1)
       in Int -> [a]
    go Int
    n

    {- ORMOLU_DISABLE -}
    {-|

    __@head xs@__ is the first element of __@xs@__. If @xs@ is empty, an 'error' is
    raised.

    \(\mathcal{O}\)(@1@).

    @head@ obeys the law:

    @
    __head__ xs = 'List.head' ('toList' xs)
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE head #-}
    head :: DList a -> a
    head :: forall a. DList a -> a
    head DList a
    xs = case DList a -> [a]
    forall a. DList a -> [a]
    toList DList a
    xs of
      a
    x : [a]
    _ -> a
    x
      [] -> [Char] -> a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Data.DList.head: empty DList"

    {- ORMOLU_DISABLE -}
    {-|

    __@tail xs@__ is a list of the elements in __@xs@__ excluding the first element.
    If @xs@ is empty, an 'error' is raised.

    \(\mathcal{O}\)(@'length' ('toList' xs)@).

    @tail@ obeys the law:

    @
    __tail__ xs = 'List.tail' ('toList' xs)
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE tail #-}
    tail :: DList a -> [a]
    tail :: forall a. DList a -> [a]
    tail DList a
    xs = case DList a -> [a]
    forall a. DList a -> [a]
    toList DList a
    xs of
      a
    _ : [a]
    ys -> [a]
    ys
      [] -> [Char] -> [a]
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Data.DList.tail: empty DList"

    {- ORMOLU_DISABLE -}
    {-|

    __@unfoldr f z@__ is the 'DList' constructed from the recursive application of
    __@f@__. The recursion starts with the seed value __@z@__ and ends when, for
    some @z' : b@, @f z' == 'Nothing'@.

    \(\mathcal{O}\)(@'length' ('List.unfoldr' f z)@).

    @unfoldr@ obeys the law:

    @
    'toList' (__unfoldr__ f z) = 'List.unfoldr' f z
    @

    -}
    {- ORMOLU_ENABLE -}

    unfoldr :: (b -> Maybe (a, b)) -> b -> DList a
    unfoldr :: forall b a. (b -> Maybe (a, b)) -> b -> DList a
    unfoldr b -> Maybe (a, b)
    f b
    z =
      case b -> Maybe (a, b)
    f b
    z of
        Maybe (a, b)
    Nothing -> DList a
    forall a. DList a
    empty
        Just (a
    x, b
    z') -> a -> DList a -> DList a
    forall a. a -> DList a -> DList a
    cons a
    x (DList a -> DList a) -> DList a -> DList a
    forall a b. (a -> b) -> a -> b
    $ (b -> Maybe (a, b)) -> b -> DList a
    forall b a. (b -> Maybe (a, b)) -> b -> DList a
    unfoldr b -> Maybe (a, b)
    f b
    z'

    {- ORMOLU_DISABLE -}
    {-|

    __@foldr f z xs@__ is the right-fold of __@f@__ over __@xs@__.

    \(\mathcal{O}\)(@'length' ('toList' xs)@).

    @foldr@ obeys the law:

    @
    __foldr__ f z xs = 'List.foldr' f z ('toList' xs)
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE foldr #-}
    foldr :: (a -> b -> b) -> b -> DList a -> b
    foldr :: forall a b. (a -> b -> b) -> b -> DList a -> b
    foldr a -> b -> b
    f b
    z = (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
    List.foldr a -> b -> b
    f b
    z ([a] -> b) -> (DList a -> [a]) -> DList a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a]
    forall a. DList a -> [a]
    toList

    {- ORMOLU_DISABLE -}
    {-|

    __@map f xs@__ is the 'DList' obtained by applying __@f@__ to each element of
    __@xs@__.

    \(\mathcal{O}\)(@'length' ('toList' xs)@).

    @map@ obeys the law:

    @
    'toList' (__map__ f xs) = 'List.map' f ('toList' xs)
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE map #-}
    map :: (a -> b) -> DList a -> DList b
    map :: forall a b. (a -> b) -> DList a -> DList b
    map a -> b
    f = (a -> DList b -> DList b) -> DList b -> DList a -> DList b
    forall a b. (a -> b -> b) -> b -> DList a -> b
    foldr (b -> DList b -> DList b
    forall a. a -> DList a -> DList a
    cons (b -> DList b -> DList b) -> (a -> b) -> a -> DList b -> DList b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> b
    f) DList b
    forall a. DList a
    empty

    {- ORMOLU_DISABLE -}
    {-|

    __@intercalate xs xss@__ is the concatenation of __@xss@__ after the insertion
    of __@xs@__ between every pair of
    elements.

    \(\mathcal{O}\)(@'length' xss@).

    @intercalate@ obeys the law:

    @
    'toList' (__intercalate__ xs xss) = 'List.intercalate' ('toList' xs) ('map' 'toList' xss)
    @

    -}
    {- ORMOLU_ENABLE -}

    {-# INLINE intercalate #-}
    intercalate :: DList a -> [DList a] -> DList a
    intercalate :: forall a. DList a -> [DList a] -> DList a
    intercalate DList a
    sep = [DList a] -> DList a
    forall a. [DList a] -> DList a
    concat ([DList a] -> DList a)
    -> ([DList a] -> [DList a]) -> [DList a] -> DList a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [DList a] -> [DList a]
    forall a. a -> [a] -> [a]
    List.intersperse DList a
    sep

    instance Eq a => Eq (DList a) where
      == :: DList a -> DList a -> Bool
    (==) = [a] -> [a] -> Bool
    forall a. Eq a => a -> a -> Bool
    (==) ([a] -> [a] -> Bool)
    -> (DList a -> [a]) -> DList a -> DList a -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` DList a -> [a]
    forall a. DList a -> [a]
    toList

    instance Ord a => Ord (DList a) where
      compare :: DList a -> DList a -> Ordering
    compare = [a] -> [a] -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare ([a] -> [a] -> Ordering)
    -> (DList a -> [a]) -> DList a -> DList a -> Ordering
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` DList a -> [a]
    forall a. DList a -> [a]
    toList

    -- The 'Read' and 'Show' instances were adapted from 'Data.Sequence'.

    instance Read a => Read (DList a) where
      readPrec :: ReadPrec (DList a)
    readPrec = ReadPrec (DList a) -> ReadPrec (DList a)
    forall a. ReadPrec a -> ReadPrec a
    Read.parens (ReadPrec (DList a) -> ReadPrec (DList a))
    -> ReadPrec (DList a) -> ReadPrec (DList a)
    forall a b. (a -> b) -> a -> b
    $
        Int -> ReadPrec (DList a) -> ReadPrec (DList a)
    forall a. Int -> ReadPrec a -> ReadPrec a
    Read.prec Int
    10 (ReadPrec (DList a) -> ReadPrec (DList a))
    -> ReadPrec (DList a) -> ReadPrec (DList a)
    forall a b. (a -> b) -> a -> b
    $ do
          Read.Ident "fromList" <- ReadPrec Lexeme
    Read.lexP
          dl <- Read.readPrec
          return (fromList dl)
      readListPrec :: ReadPrec [DList a]
    readListPrec = ReadPrec [DList a]
    forall a. Read a => ReadPrec [a]
    Read.readListPrecDefault

    instance Show a => Show (DList a) where
      showsPrec :: Int -> DList a -> ShowS
    showsPrec Int
    p DList a
    dl =
        Bool -> ShowS -> ShowS
    showParen (Int
    p Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    10) (ShowS -> ShowS) -> ShowS -> ShowS
    forall a b. (a -> b) -> a -> b
    $
          [Char] -> ShowS
    showString [Char]
    "fromList " ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [a] -> ShowS
    forall a. Show a => a -> ShowS
    shows (DList a -> [a]
    forall a. DList a -> [a]
    toList DList a
    dl)

    instance Monoid.Monoid (DList a) where
      {-# INLINE mempty #-}
      mempty :: DList a
    mempty = DList a
    forall a. DList a
    empty

    -- CPP: base >= 4.11 for Semigroup as a superclass of Monoid
    #if MIN_VERSION_base(4,11,0)

    #else

      {-# INLINE mappend #-}
    -- CPP: base >= 4.9 for Semigroup in base
    #if MIN_VERSION_base(4,9,0)
      -- Canonical definition
      mappend = (Semigroup.<>)
    #else
      mappend = append
    #endif

    #endif

    instance Functor DList where
      {-# INLINE fmap #-}
      fmap :: forall a b. (a -> b) -> DList a -> DList b
    fmap = (a -> b) -> DList a -> DList b
    forall a b. (a -> b) -> DList a -> DList b
    map

    instance Applicative.Applicative DList where
      {-# INLINE pure #-}
      pure :: forall a. a -> DList a
    pure = a -> DList a
    forall a. a -> DList a
    singleton

      {-# INLINE (<*>) #-}
      <*> :: forall a b. DList (a -> b) -> DList a -> DList b
    (<*>) = DList (a -> b) -> DList a -> DList b
    forall (m :: * -> *) a b. Monad m => m (a -> b) -> m a -> m b
    Monad.ap

    instance Applicative.Alternative DList where
      {-# INLINE empty #-}
      empty :: forall a. DList a
    empty = DList a
    forall a. DList a
    empty

      {-# INLINE (<|>) #-}
      <|> :: forall a. DList a -> DList a -> DList a
    (<|>) = DList a -> DList a -> DList a
    forall a. DList a -> DList a -> DList a
    append

    instance Monad DList where
      {-# INLINE (>>=) #-}
      DList a
    m >>= :: forall a b. DList a -> (a -> DList b) -> DList b
    >>= a -> DList b
    k =
        -- = concat (toList (fmap k m))
        -- = (concat . toList . fromList . List.map k . toList) m
        -- = concat . List.map k . toList $ m
        -- = List.foldr append empty . List.map k . toList $ m
        -- = List.foldr (append . k) empty . toList $ m
        (a -> DList b -> DList b) -> DList b -> DList a -> DList b
    forall a b. (a -> b -> b) -> b -> DList a -> b
    foldr (DList b -> DList b -> DList b
    forall a. DList a -> DList a -> DList a
    append (DList b -> DList b -> DList b)
    -> (a -> DList b) -> a -> DList b -> DList b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> DList b
    k) DList b
    forall a. DList a
    empty DList a
    m

      {-# INLINE return #-}
      return :: forall a. a -> DList a
    return = a -> DList a
    forall a. a -> DList a
    forall (f :: * -> *) a. Applicative f => a -> f a
    Applicative.pure

    -- CPP: base < 4.13 for fail in Monad
    #if !MIN_VERSION_base(4,13,0)
      {-# INLINE fail #-}
      fail _ = empty
    #endif

    -- CPP: base >= 4.9 for MonadFail
    #if MIN_VERSION_base(4,9,0)
    instance Monad.MonadFail DList where
      {-# INLINE fail #-}
      fail :: forall a. [Char] -> DList a
    fail [Char]
    _ = DList a
    forall a. DList a
    empty
    #endif

    instance Monad.MonadPlus DList where
      {-# INLINE mzero #-}
      mzero :: forall a. DList a
    mzero = DList a
    forall a. DList a
    empty

      {-# INLINE mplus #-}
      mplus :: forall a. DList a -> DList a -> DList a
    mplus = DList a -> DList a -> DList a
    forall a. DList a -> DList a -> DList a
    append

    instance Foldable.Foldable DList where
      {-# INLINE fold #-}
      fold :: forall m. Monoid m => DList m -> m
    fold = [m] -> m
    forall a. Monoid a => [a] -> a
    Monoid.mconcat ([m] -> m) -> (DList m -> [m]) -> DList m -> m
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList m -> [m]
    forall a. DList a -> [a]
    toList

      {-# INLINE foldMap #-}
      foldMap :: forall m a. Monoid m => (a -> m) -> DList a -> m
    foldMap a -> m
    f = (a -> m) -> [a] -> m
    forall m a. Monoid m => (a -> m) -> [a] -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    Foldable.foldMap a -> m
    f ([a] -> m) -> (DList a -> [a]) -> DList a -> m
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a]
    forall a. DList a -> [a]
    toList

      {-# INLINE foldr #-}
      foldr :: forall a b. (a -> b -> b) -> b -> DList a -> b
    foldr a -> b -> b
    f b
    x = (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
    List.foldr a -> b -> b
    f b
    x ([a] -> b) -> (DList a -> [a]) -> DList a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a]
    forall a. DList a -> [a]
    toList

      {-# INLINE foldl #-}
      foldl :: forall b a. (b -> a -> b) -> b -> DList a -> b
    foldl b -> a -> b
    f b
    x = (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
    List.foldl b -> a -> b
    f b
    x ([a] -> b) -> (DList a -> [a]) -> DList a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a]
    forall a. DList a -> [a]
    toList

      {-# INLINE foldr1 #-}
      foldr1 :: forall a. (a -> a -> a) -> DList a -> a
    foldr1 a -> a -> a
    f = (a -> a -> a) -> [a] -> a
    forall a. (a -> a -> a) -> [a] -> a
    forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
    List.foldr1 a -> a -> a
    f ([a] -> a) -> (DList a -> [a]) -> DList a -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a]
    forall a. DList a -> [a]
    toList

      {-# INLINE foldl1 #-}
      foldl1 :: forall a. (a -> a -> a) -> DList a -> a
    foldl1 a -> a -> a
    f = (a -> a -> a) -> [a] -> a
    forall a. (a -> a -> a) -> [a] -> a
    forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
    List.foldl1 a -> a -> a
    f ([a] -> a) -> (DList a -> [a]) -> DList a -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a]
    forall a. DList a -> [a]
    toList

    -- CPP: GHC >= 7.6 for foldl', foldr' in Foldable
    #if __GLASGOW_HASKELL__ >= 706
      {-# INLINE foldl' #-}
      foldl' :: forall b a. (b -> a -> b) -> b -> DList a -> b
    foldl' b -> a -> b
    f b
    x = (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
    List.foldl' b -> a -> b
    f b
    x ([a] -> b) -> (DList a -> [a]) -> DList a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a]
    forall a. DList a -> [a]
    toList

      {-# INLINE foldr' #-}
      foldr' :: forall a b. (a -> b -> b) -> b -> DList a -> b
    foldr' a -> b -> b
    f b
    x = (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
    Foldable.foldr' a -> b -> b
    f b
    x ([a] -> b) -> (DList a -> [a]) -> DList a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a]
    forall a. DList a -> [a]
    toList
    #endif

    -- CPP: base >= 4.8 for toList in Foldable
    #if MIN_VERSION_base(4,8,0)
      {-# INLINE toList #-}
      toList :: forall a. DList a -> [a]
    toList = DList a -> [a]
    forall a. DList a -> [a]
    Data.DList.Internal.toList
    #endif

    instance Traversable.Traversable DList where
      {-# INLINE traverse #-}
      traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> DList a -> f (DList b)
    traverse a -> f b
    f = (a -> f (DList b) -> f (DList b))
    -> f (DList b) -> DList a -> f (DList b)
    forall a b. (a -> b -> b) -> b -> DList a -> b
    foldr a -> f (DList b) -> f (DList b)
    cons_f (DList b -> f (DList b)
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    Applicative.pure DList b
    forall a. DList a
    empty)
        where
          cons_f :: a -> f (DList b) -> f (DList b)
    cons_f a
    x = (b -> DList b -> DList b) -> f b -> f (DList b) -> f (DList b)
    forall a b c. (a -> b -> c) -> f a -> f b -> f c
    forall (f :: * -> *) a b c.
    Applicative f =>
    (a -> b -> c) -> f a -> f b -> f c
    Applicative.liftA2 b -> DList b -> DList b
    forall a. a -> DList a -> DList a
    cons (a -> f b
    f a
    x)

    instance NFData a => NFData (DList a) where
      {-# INLINE rnf #-}
      rnf :: DList a -> ()
    rnf = [a] -> ()
    forall a. NFData a => a -> ()
    rnf ([a] -> ()) -> (DList a -> [a]) -> DList a -> ()
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . DList a -> [a]
    forall a. DList a -> [a]
    toList

    {-

    The 'IsString' instance is _not_ a flexible instance to allow certain uses of
    overloaded strings. See tests/OverloadedStrings.hs for an example and
    https://gitlab.haskell.org/ghc/ghc/-/commit/b225b234a6b11e42fef433dcd5d2a38bb4b466bf
    for the same change made to the IsString instance for lists.

    -}

    instance a ~ Char => IsString (DList a) where
      {-# INLINE fromString #-}
      fromString :: [Char] -> DList a
    fromString = [Char] -> DList a
    [Char] -> DList Char
    forall a. [a] -> DList a
    fromList

    -- CPP: GHC >= 7.8 for IsList
    #if __GLASGOW_HASKELL__ >= 708
    instance Exts.IsList (DList a) where
      type Item (DList a) = a

      {-# INLINE fromList #-}
      fromList :: [Item (DList a)] -> DList a
    fromList = [a] -> DList a
    [Item (DList a)] -> DList a
    forall a. [a] -> DList a
    fromList

      {-# INLINE toList #-}
      toList :: DList a -> [Item (DList a)]
    toList = DList a -> [a]
    DList a -> [Item (DList a)]
    forall a. DList a -> [a]
    toList
    #endif

    {-

    We use 'compare n 0' in the definition of 'Semigroup.stimes' since the same
    expression is used in 'Semigroup.stimesMonoid' and we should get a lazy
    advantage. However, we prefer the error to be sourced here instead of
    'Semigroup.stimesMonoid'.

    -}

    -- CPP: base >= 4.9 for Semigroup
    #if MIN_VERSION_base(4,9,0)
    instance Semigroup.Semigroup (DList a) where
      {-# INLINE (<>) #-}
      <> :: DList a -> DList a -> DList a
    (<>) = DList a -> DList a -> DList a
    forall a. DList a -> DList a -> DList a
    append

      stimes :: forall b. Integral b => b -> DList a -> DList a
    stimes b
    n = case b -> b -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare b
    n b
    0 of
        Ordering
    LT -> [Char] -> DList a -> DList a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Data.DList.stimes: negative multiplier"
        Ordering
    _ -> b -> DList a -> DList a
    forall b a. (Integral b, Monoid a) => b -> a -> a
    Semigroup.stimesMonoid b
    n
    #endif