-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Difference lists
--   
--   Difference lists are a list-like type supporting O(1) append. This is
--   particularly useful for efficient logging and pretty printing (e.g.
--   with the Writer monad), where list append quickly becomes too
--   expensive.
@package dlist
@version 0.8.0.2


-- | Difference lists: a data structure for <i>O(1)</i> append on lists.
module Data.DList

-- | 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 <i>O(1)</i> append and snoc operations on
--   lists, making it very useful for append-heavy uses (esp. left-nested
--   uses of <a>++</a>), such as logging and pretty printing.
--   
--   Here is an example using DList as the state type when printing a tree
--   with the Writer monad:
--   
--   <pre>
--   import Control.Monad.Writer
--   import Data.DList
--   
--   data Tree a = Leaf a | Branch (Tree a) (Tree a)
--   
--   flatten_writer :: Tree x -&gt; DList x
--   flatten_writer = snd . runWriter . flatten
--       where
--         flatten (Leaf x)     = tell (singleton x)
--         flatten (Branch x y) = flatten x &gt;&gt; flatten y
--   </pre>
data DList a

-- | Convert a list to a dlist
fromList :: [a] -> DList a

-- | Convert a dlist to a list
toList :: DList a -> [a]

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

-- | Create a dlist containing no elements
empty :: DList a

-- | Create dlist with a single element
singleton :: a -> DList a

-- | <i>O(1)</i>. Prepend a single element to a dlist
cons :: a -> DList a -> DList a
infixr 9 `cons`

-- | <i>O(1)</i>. Append a single element to a dlist
snoc :: DList a -> a -> DList a
infixl 9 `snoc`

-- | <i>O(1)</i>. Append dlists
append :: DList a -> DList a -> DList a

-- | <i>O(spine)</i>. Concatenate dlists
concat :: [DList a] -> DList a

-- | <i>O(n)</i>. Create a dlist of the given number of elements
replicate :: Int -> a -> DList a

-- | <i>O(n)</i>. List elimination for dlists
list :: b -> (a -> DList a -> b) -> DList a -> b

-- | <i>O(n)</i>. Return the head of the dlist
head :: DList a -> a

-- | <i>O(n)</i>. Return the tail of the dlist
tail :: DList a -> DList a

-- | <i>O(n)</i>. Unfoldr for dlists
unfoldr :: (b -> Maybe (a, b)) -> b -> DList a

-- | <i>O(n)</i>. Foldr over difference lists
foldr :: (a -> b -> b) -> b -> DList a -> b

-- | <i>O(n)</i>. Map over difference lists.
map :: (a -> b) -> DList a -> DList b
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.DList.DList a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.DList.DList a)
instance GHC.Read.Read a => GHC.Read.Read (Data.DList.DList a)
instance GHC.Show.Show a => GHC.Show.Show (Data.DList.DList a)
instance GHC.Base.Monoid (Data.DList.DList a)
instance GHC.Base.Functor Data.DList.DList
instance GHC.Base.Applicative Data.DList.DList
instance GHC.Base.Alternative Data.DList.DList
instance GHC.Base.Monad Data.DList.DList
instance GHC.Base.MonadPlus Data.DList.DList
instance Data.Foldable.Foldable Data.DList.DList
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.DList.DList a)
instance a ~ GHC.Types.Char => Data.String.IsString (Data.DList.DList a)
instance GHC.Exts.IsList (Data.DList.DList a)
instance Data.Semigroup.Semigroup (Data.DList.DList a)