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


-- | Differences lists
--   
--   Differences lists: 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.3.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 at the given list
--   
--   This structure supports <i>O(1)</i> append and snoc operations on
--   lists, making it very useful for append-heavy uses, such as logging
--   and pretty printing.
--   
--   For 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>
newtype DList a
DL :: ([a] -> [a]) -> DList a
unDL :: DList a -> [a] -> [a]

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

-- | Converting a dlist back to a normal list
toList :: DList a -> [a]

-- | Create a difference list containing no elements
empty :: DList a

-- | Create difference list with given single element
singleton :: a -> DList a

-- | <i>O(1)</i>, Prepend a single element to a difference list
cons :: a -> DList a -> DList a

-- | <i>O(1)</i>, Append a single element at a difference list
snoc :: DList a -> a -> DList a

-- | <i>O(1)</i>, Appending difference lists
append :: DList a -> DList a -> DList a

-- | <i>O(spine)</i>, Concatenate difference lists
concat :: [DList a] -> DList a

-- | <i>O(length dl)</i>, List elimination, head, tail.
list :: b -> (a -> DList a -> b) -> DList a -> b

-- | Return the head of the list
head :: DList a -> a

-- | Return the tail of the list
tail :: DList a -> DList a

-- | Unfoldr for difference lists
unfoldr :: (b -> Maybe (a, b)) -> b -> DList a

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

-- | Map over difference lists.
map :: (a -> b) -> DList a -> DList b
maybeReturn :: (MonadPlus m) => Maybe a -> m a
instance MonadPlus DList
instance Monad DList
instance Applicative DList
instance Functor DList
instance Monoid (DList a)