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


-- | Differences lists
--   
--   Differences lists: a list-like type supporting O(1) append
@package dlist
@version 0.3


-- | 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.
data DList 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 Functor DList
instance Monoid (DList a)