{-# OPTIONS_GHC -O2 #-}
{-# OPTIONS_HADDOCK prune #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE TypeFamilies #-} -- For the IsList and IsString instances

#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 708
{-# LANGUAGE PatternSynonyms #-}
-- Mark this module as trustworthy even though we import 'IsList' from GHC.Exts,
-- which is marked unsafe. 'IsList' is safe.
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE ViewPatterns #-}
#endif

-----------------------------------------------------------------------------
-- |
-- Module      :  Data.DList
-- Copyright   :  (c) 2006-2009 Don Stewart, 2013-2019 Sean Leather
-- License     :  See LICENSE file
--
-- Maintainer  :  sean.leather@gmail.com
-- Stability   :  stable
-- Portability :  portable
--
-- Difference lists: a data structure for /O(1)/ append on lists.
--
-----------------------------------------------------------------------------

module Data.DList

#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 800
  ( DList(Nil, Cons)
#else
  ( DList
#endif

  -- * Construction
  , fromList
  , toList
  , apply

  -- * Basic functions
  , empty
  , singleton
  , cons
  , snoc
  , append
  , concat
  , replicate
  , list
  , head
  , tail
  , unfoldr
  , foldr
  , map

#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 708 && __GLASGOW_HASKELL__ < 800
  -- * Pattern Synonyms
  , pattern Nil
  , pattern Cons
#endif

  ) where

import Prelude hiding (concat, foldr, map, head, tail, replicate)
import qualified Data.List as List
import Control.DeepSeq (NFData(..))
import Control.Monad as M
import Data.Function (on)
import Data.String (IsString(..))

import qualified Data.Foldable as F

#if !MIN_VERSION_base(4,8,0)
import Data.Monoid
import Data.Foldable (Foldable)
import Control.Applicative(Applicative(..))
#endif

#if MIN_VERSION_base(4,9,0)
import Data.Semigroup (Semigroup(..))
#if !MIN_VERSION_base(4,13,0)
import Control.Monad.Fail (MonadFail(..))
#endif
#endif

#ifdef __GLASGOW_HASKELL__

import Text.Read (Lexeme(Ident), lexP, parens, prec, readPrec, readListPrec,
                  readListPrecDefault)

#if __GLASGOW_HASKELL__ >= 708
import GHC.Exts (IsList)
-- Make IsList type and methods visible for instance.
import qualified GHC.Exts (IsList(Item, fromList, toList))
#endif

#endif

import Control.Applicative(Alternative, (<|>))
import qualified Control.Applicative (empty)

-- | A difference list is a function that, given a list, returns the original
-- contents of the difference list prepended to the given list.
--
-- This structure supports /O(1)/ append and snoc operations on lists, making it
-- very useful for append-heavy uses (esp. left-nested uses of 'List.++'), such
-- as logging and pretty printing.
--
-- Here is an example using DList as the state type when printing a tree with
-- the Writer monad:
--
-- > import Control.Monad.Writer
-- > import Data.DList
-- >
-- > data Tree a = Leaf a | Branch (Tree a) (Tree a)
-- >
-- > flatten_writer :: Tree x -> DList x
-- > flatten_writer = snd . runWriter . flatten
-- >     where
-- >       flatten (Leaf x)     = tell (singleton x)
-- >       flatten (Branch x y) = flatten x >> flatten y
--
newtype DList a = DL { DList a -> [a] -> [a]
unDL :: [a] -> [a] }

-- | Convert a list to a dlist
fromList    :: [a] -> DList a
fromList :: [a] -> DList a
fromList    = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DL (([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]
(++)
{-# INLINE fromList #-}

-- | Convert a dlist to a list
toList      :: DList a -> [a]
toList :: 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]
unDL
{-# INLINE toList #-}

#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 708
-- | A unidirectional pattern synonym using 'toList' in a view pattern and
-- matching on @[]@
#if __GLASGOW_HASKELL__ >= 710
pattern Nil :: DList a
#endif
pattern $mNil :: forall r a. DList a -> (Void# -> r) -> (Void# -> r) -> r
Nil <- (toList -> [])

-- | A unidirectional pattern synonym using 'toList' in a view pattern and
-- matching on @x:xs@ such that you have the pattern @Cons x xs@
#if __GLASGOW_HASKELL__ >= 710
pattern Cons :: a -> [a] -> DList a
#endif
pattern $mCons :: forall r a. DList a -> (a -> [a] -> r) -> (Void# -> r) -> r
Cons x xs <- (toList -> x:xs)
#endif

-- | Apply a dlist to a list to get the underlying list with an extension
--
-- > apply (fromList xs) ys = xs ++ ys
apply       :: DList a -> [a] -> [a]
apply :: DList a -> [a] -> [a]
apply       = DList a -> [a] -> [a]
forall a. DList a -> [a] -> [a]
unDL

-- | Create a dlist containing no elements
empty       :: DList a
empty :: DList a
empty       = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DL [a] -> [a]
forall a. a -> a
id
{-# INLINE empty #-}

-- | Create dlist with a single element
singleton   :: a -> DList a
singleton :: a -> DList a
singleton   = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DL (([a] -> [a]) -> DList a) -> (a -> [a] -> [a]) -> a -> DList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (:)
{-# INLINE singleton #-}

-- | /O(1)/. Prepend a single element to a dlist
infixr `cons`
cons        :: a -> DList a -> DList a
cons :: a -> DList a -> DList a
cons a
x DList a
xs   = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DL ((a
xa -> [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]
unDL DList a
xs)
{-# INLINE cons #-}

-- | /O(1)/. Append a single element to a dlist
infixl `snoc`
snoc        :: DList a -> a -> DList a
snoc :: DList a -> a -> DList a
snoc DList a
xs a
x   = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DL (DList a -> [a] -> [a]
forall a. DList a -> [a] -> [a]
unDL DList a
xs ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:))
{-# INLINE snoc #-}

-- | /O(1)/. Append dlists
append       :: DList a -> DList a -> DList a
append :: DList a -> DList a -> DList a
append DList a
xs DList a
ys = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DL (DList a -> [a] -> [a]
forall a. DList a -> [a] -> [a]
unDL 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]
unDL DList a
ys)
{-# INLINE append #-}

-- | /O(spine)/. Concatenate dlists
concat       :: [DList a] -> DList a
concat :: [DList a] -> DList a
concat       = (DList a -> DList a -> DList a) -> DList a -> [DList a] -> DList a
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
{-# INLINE concat #-}

-- | /O(n)/. Create a dlist of the given number of elements
replicate :: Int -> a -> DList a
replicate :: Int -> a -> DList a
replicate Int
n a
x = ([a] -> [a]) -> DList a
forall a. ([a] -> [a]) -> DList a
DL (([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
mInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
                            in Int -> [a]
go Int
n
{-# INLINE replicate #-}

-- | /O(n)/. List elimination for dlists
list :: b -> (a -> DList a -> b) -> DList a -> b
list :: b -> (a -> DList a -> b) -> DList a -> b
list b
nill a -> DList a -> b
consit DList a
dl =
  case DList a -> [a]
forall a. DList a -> [a]
toList DList a
dl of
    [] -> b
nill
    (a
x : [a]
xs) -> a -> DList a -> b
consit a
x ([a] -> DList a
forall a. [a] -> DList a
fromList [a]
xs)

-- | /O(1)/. Return the head of the dlist
head :: DList a -> a
head :: DList a -> a
head = a -> (a -> DList a -> a) -> DList a -> a
forall b a. b -> (a -> DList a -> b) -> DList a -> b
list ([Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.DList.head: empty dlist") a -> DList a -> a
forall a b. a -> b -> a
const

-- | /O(n)/. Return the tail of the dlist
tail :: DList a -> DList a
tail :: DList a -> DList a
tail = DList a -> (a -> DList a -> DList a) -> DList a -> DList a
forall b a. b -> (a -> DList a -> b) -> DList a -> b
list ([Char] -> DList a
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.DList.tail: empty dlist") ((DList a -> a -> DList a) -> a -> DList a -> DList a
forall a b c. (a -> b -> c) -> b -> a -> c
flip DList a -> a -> DList a
forall a b. a -> b -> a
const)

-- | /O(n)/. Unfoldr for dlists
unfoldr :: (b -> Maybe (a, b)) -> b -> DList a
unfoldr :: (b -> Maybe (a, b)) -> b -> DList a
unfoldr b -> Maybe (a, b)
pf b
b =
  case b -> Maybe (a, b)
pf b
b of
    Maybe (a, b)
Nothing     -> DList a
forall a. DList a
empty
    Just (a
a, b
b') -> a -> DList a -> DList a
forall a. a -> DList a -> DList a
cons a
a ((b -> Maybe (a, b)) -> b -> DList a
forall b a. (b -> Maybe (a, b)) -> b -> DList a
unfoldr b -> Maybe (a, b)
pf b
b')

-- | /O(n)/. Foldr over difference lists
foldr        :: (a -> b -> b) -> b -> DList a -> b
foldr :: (a -> b -> b) -> b -> DList a -> b
foldr a -> b -> b
f b
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
b ([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 #-}

-- | /O(n)/. Map over difference lists.
map          :: (a -> b) -> DList a -> DList b
map :: (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
{-# INLINE map #-}

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
#ifdef __GLASGOW_HASKELL__
  readPrec :: ReadPrec (DList a)
readPrec = ReadPrec (DList a) -> ReadPrec (DList a)
forall a. ReadPrec a -> ReadPrec a
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
prec Int
10 (ReadPrec (DList a) -> ReadPrec (DList a))
-> ReadPrec (DList a) -> ReadPrec (DList a)
forall a b. (a -> b) -> a -> b
$ do
    Ident [Char]
"fromList" <- ReadPrec Lexeme
lexP
    [a]
dl <- ReadPrec [a]
forall a. Read a => ReadPrec a
readPrec
    DList a -> ReadPrec (DList a)
forall (m :: * -> *) a. Monad m => a -> m a
return ([a] -> DList a
forall a. [a] -> DList a
fromList [a]
dl)
  readListPrec :: ReadPrec [DList a]
readListPrec = ReadPrec [DList a]
forall a. Read a => ReadPrec [a]
readListPrecDefault
#else
  readsPrec p = readParen (p > 10) $ \r -> do
    ("fromList", s) <- lex r
    (dl, t) <- reads s
    return (fromList dl, t)
#endif

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 (DList a) where
    mempty :: DList a
mempty  = DList a
forall a. DList a
empty
    mappend :: DList a -> DList a -> DList a
mappend = DList a -> DList a -> DList a
forall a. DList a -> DList a -> DList a
append

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

instance Applicative DList where
    pure :: a -> DList a
pure  = a -> DList a
forall a. a -> DList a
singleton
    {-# INLINE pure #-}
    <*> :: 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
ap

instance Alternative DList where
    empty :: DList a
empty = DList a
forall a. DList a
empty
    <|> :: 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
  DList a
m >>= :: 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 :: a -> DList a
return   = a -> DList a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
  {-# INLINE return #-}

#if !MIN_VERSION_base(4,13,0)
  fail _   = empty
  {-# INLINE fail #-}
#endif

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

instance MonadPlus DList where
  mzero :: DList a
mzero    = DList a
forall a. DList a
empty
  mplus :: DList a -> DList a -> DList a
mplus    = DList a -> DList a -> DList a
forall a. DList a -> DList a -> DList a
append

instance Foldable DList where
  fold :: DList m -> m
fold        = [m] -> m
forall a. Monoid a => [a] -> a
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 fold #-}

  foldMap :: (a -> m) -> DList a -> m
foldMap a -> m
f   = (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
F.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 foldMap #-}

  foldr :: (a -> b -> b) -> b -> DList a -> b
foldr a -> b -> b
f b
x   = (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 foldr #-}

  foldl :: (b -> a -> b) -> b -> DList a -> b
foldl b -> a -> b
f b
x   = (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 foldl #-}

  foldr1 :: (a -> a -> a) -> DList a -> a
foldr1 a -> a -> a
f    = (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 foldr1 #-}

  foldl1 :: (a -> a -> a) -> DList a -> a
foldl1 a -> a -> a
f    = (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
  {-# INLINE foldl1 #-}

-- CPP: foldl', foldr' added to Foldable in 7.6.1
-- http://www.haskell.org/ghc/docs/7.6.1/html/users_guide/release-7-6-1.html
#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 706
  foldl' :: (b -> a -> b) -> b -> DList a -> b
foldl' b -> a -> b
f b
x  = (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 foldl' #-}

  foldr' :: (a -> b -> b) -> b -> DList a -> b
foldr' a -> b -> b
f b
x  = (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
F.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 foldr' #-}
#endif

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

instance NFData a => NFData (DList a) where
  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
  {-# INLINE rnf #-}

-- This is _not_ a flexible instance to allow certain uses of overloaded
-- strings. See tests/OverloadedStrings.hs for an example and
-- https://git.haskell.org/ghc.git/commitdiff/b225b234a6b11e42fef433dcd5d2a38bb4b466bf
-- for the same change made to the IsString instance for lists.
instance a ~ Char => IsString (DList a) where
  fromString :: [Char] -> DList a
fromString = [Char] -> DList a
forall a. [a] -> DList a
fromList
  {-# INLINE fromString #-}

#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 708
instance IsList (DList a) where
  type Item (DList a) = a
  fromList :: [Item (DList a)] -> DList a
fromList = [Item (DList a)] -> DList a
forall a. [a] -> DList a
fromList
  {-# INLINE fromList #-}
  toList :: DList a -> [Item (DList a)]
toList = DList a -> [Item (DList a)]
forall a. DList a -> [a]
toList
  {-# INLINE toList #-}
#endif

#if MIN_VERSION_base(4,9,0)
instance Semigroup (DList a) where
  <> :: DList a -> DList a -> DList a
(<>) = DList a -> DList a -> DList a
forall a. DList a -> DList a -> DList a
append
  {-# INLINE (<>) #-}
  stimes :: b -> DList a -> DList a
stimes b
n DList a
x
    | b
n b -> b -> Bool
forall a. Ord a => a -> a -> Bool
< b
0     = [Char] -> DList a
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.DList.stimes: negative multiplier"
    | Bool
otherwise = b -> DList a
rep b
n
    where
      rep :: b -> DList a
rep b
0 = DList a
forall a. DList a
empty
      rep b
i = DList a
x DList a -> DList a -> DList a
forall a. Semigroup a => a -> a -> a
<> b -> DList a
rep (b -> b
forall a. Enum a => a -> a
pred b
i)
#endif