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


-- | Difference lists
--   
@package dlist
@version 0.7.1.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

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

-- | <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 IsList (DList a)
instance IsString (DList Char)
instance NFData a => NFData (DList a)
instance Foldable DList
instance MonadPlus DList
instance Monad DList
instance Alternative DList
instance Applicative DList
instance Functor DList
instance Monoid (DList a)
instance Show a => Show (DList a)
instance Read a => Read (DList a)
instance Ord a => Ord (DList a)
instance Eq a => Eq (DList a)