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


-- | Difference strings.
--   
--   Difference strings: a data structure for O(1) append on strings. Note
--   that a DString is just a newtype wrapper around a 'DList Char'. The
--   reason we need a new type instead of just a type synonym is that we
--   can have an 'instance IsString DString' so we can write overloaded
--   string literals of type DString.
@package dstring
@version 0.3


-- | Difference strings: a data structure for O(1) append on strings. Note
--   that a DString is just a newtype wrapper around a 'DList Char'. The
--   reason we need a new type instead of just a type synonym is that we
--   can have an 'instance IsString DString' so we can write overloaded
--   string literals of type DString.
module Data.DString

-- | A difference string is a function that given a string, returns the
--   original contents of the difference string prepended at the given
--   string.
--   
--   This structure supports O(1) <tt>append</tt> en <tt>snoc</tt>
--   operations on strings making it very usefull for append-heavy uses
--   such as logging and pretty printing.
--   
--   You can use it to efficiently show a tree for example: (Note that we
--   make use of some functions from the <i>string-combinators</i> package:
--   <a>http://hackage.haskell.org/cgi-bin/hackage-scripts/package/string-combinators</a>)
--   
--   <pre>
--   {-# LANGUAGE OverloadedStrings #-}
--   
--   import Data.DString
--   import Data.String.Combinators ((&lt;+&gt;), fromShow, paren)
--   
--   data Tree a = Leaf a | Branch (Tree a) (Tree a)
--   
--   instance Show a =&gt; Show (Tree a) where
--       show = toString . go
--           where
--             go (Leaf x)     = "Leaf" &lt;+&gt; fromShow x
--             go (Branch l r) = "Branch" &lt;+&gt; paren (go l) &lt;+&gt; paren (go r)
--   </pre>
data DString

-- | Convert a difference list of Chars to a difference string
fromDList :: DList Char -> DString

-- | Convert a difference string to a difference list
toDList :: DString -> DList Char

-- | Convert a ShowS to a difference string
fromShowS :: ShowS -> DString

-- | Convert a difference string to a ShowS
toShowS :: DString -> ShowS

-- | Build a difference string from a single Char
singleton :: Char -> DString

-- | <i>O(1)</i>, Prepend a Char to a difference string
cons :: Char -> DString -> DString

-- | <i>O(1)</i>, Append a Char to a difference string
snoc :: DString -> Char -> DString

-- | <i>O(spine)</i>, Concatenate difference strings
concat :: [DString] -> DString

-- | <i>O(length ds)</i>, difference list elimination, head, tail.
list :: b -> (Char -> DString -> b) -> DString -> b

-- | Return the head of the difference string
head :: DString -> Char

-- | Return the tail of the difference string
tail :: DString -> DString

-- | Unfoldr for difference strings
unfoldr :: (b -> Maybe (Char, b)) -> b -> DString

-- | Foldr over difference strings
foldr :: (Char -> b -> b) -> b -> DString -> b
instance Monoid DString
instance Show DString
instance ToString DString
instance IsString DString