-- 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.7.1.2

-- | Difference lists: a data structure for O(1) 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 O(1) append and snoc operations on
--   lists, making it very useful for append-heavy uses (esp. left-nested
--   uses of ++), 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
--   
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
--   
--   
--   apply (fromList xs) ys = xs ++ ys
--   
apply :: DList a -> [a] -> [a]

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

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

-- | O(1). Prepend a single element to a dlist
cons :: a -> DList a -> DList a

-- | O(1). Append a single element to a dlist
snoc :: DList a -> a -> DList a

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

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

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

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

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

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

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

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

-- | O(n). 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 Data.String.IsString (Data.DList.DList GHC.Types.Char)
instance GHC.Exts.IsList (Data.DList.DList a)
