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


-- | Difference lists
--   
--   List-like types supporting O(1) append and snoc operations.
@package dlist
@version 1.0


-- | A <b>difference list</b> is an abstraction representing a list that
--   supports &lt;math&gt;(<tt>1</tt>) <a>append</a> and <a>snoc</a>
--   operations. This module provides the type for a difference list,
--   <a>DList</a>, and a collection of supporting functions for (a)
--   converting to and from lists and (b) operating on <a>DList</a>s
--   efficiently.
module Data.DList

-- | A difference list is an abstraction representing a list that supports
--   &lt;math&gt;(<tt>1</tt>) <a>append</a> and <a>snoc</a> operations,
--   making it useful for replacing frequent applications of <a>++</a> such
--   as logging and pretty printing (esp. if those uses of <a>++</a> are
--   left-nested).
data DList a

-- | A unidirectional pattern synonym for <a>empty</a>. This is implemented
--   with <a>toList</a>.
pattern Nil :: DList a

-- | A unidirectional pattern synonym for <a>cons</a>. This is implemented
--   with <a>toList</a>.
pattern Cons :: a -> [a] -> DList a

-- | <b><tt>fromList xs</tt></b> is a <a>DList</a> representing the list
--   <b><tt>xs</tt></b>.
--   
--   <tt>fromList</tt> obeys the laws:
--   
--   <pre>
--   <a>toList</a> . <b>fromList</b> = <a>id</a>
--   <b>fromList</b> . <a>toList</a> = <a>id</a>
--   </pre>
--   
--   This function is implemented with <a>++</a>. Repeated uses of
--   <tt>fromList</tt> are just as inefficient as repeated uses of
--   <a>++</a>. If you find yourself doing some form of the following
--   (possibly indirectly), you may not be taking advantage of the
--   <a>DList</a> representation and library:
--   
--   <pre>
--   <b>fromList</b> . f . <a>toList</a>
--   </pre>
--   
--   More likely, you will convert from a list, perform some operation on
--   the <a>DList</a>, and convert back to a list:
--   
--   <pre>
--   <a>toList</a> . g . <b>fromList</b>
--   </pre>
fromList :: [a] -> DList a

-- | <b><tt>toList xs</tt></b> is the list represented by
--   <b><tt>xs</tt></b>.
--   
--   <tt>toList</tt> obeys the laws:
--   
--   <pre>
--   <b>toList</b> . <a>fromList</a> = <a>id</a>
--   <a>fromList</a> . <b>toList</b> = <a>id</a>
--   </pre>
--   
--   Evaluating <tt>toList xs</tt> may “collapse” the chain of function
--   composition underlying many <a>DList</a> functions (<a>append</a> in
--   particular) used to construct <tt>xs</tt>. This may affect any
--   efficiency you achieved due to laziness in the construction.
toList :: DList a -> [a]

-- | <b><tt>apply xs ys</tt></b> is the list represented by the
--   <b><tt>xs</tt></b> after appending <b><tt>ys</tt></b> to it.
--   
--   &lt;math&gt;(<tt>1</tt>).
--   
--   <tt>apply</tt> obeys the law:
--   
--   <pre>
--   <b>apply</b> xs ys = <a>toList</a> xs <a>++</a> ys
--   </pre>
apply :: DList a -> [a] -> [a]

-- | <b><tt>empty</tt></b> is a <a>DList</a> with no elements.
--   
--   <tt>empty</tt> obeys the law:
--   
--   <pre>
--   <a>toList</a> <b>empty</b> = []
--   </pre>
empty :: DList a

-- | <b><tt>singleton x</tt></b> is a <a>DList</a> with the single element
--   <b><tt>x</tt></b>.
--   
--   <tt>singleton</tt> obeys the law:
--   
--   <pre>
--   <a>toList</a> (<b>singleton</b> x) = [x]
--   </pre>
singleton :: a -> DList a

-- | <b><tt>cons x xs</tt></b> is a <a>DList</a> with the <a>head</a>
--   <b><tt>x</tt></b> and the <a>tail</a> <b><tt>xs</tt></b>.
--   
--   &lt;math&gt;(<tt>1</tt>).
--   
--   <tt>cons</tt> obeys the law:
--   
--   <pre>
--   <a>toList</a> (<b>cons</b> x xs) = x : <a>toList</a> xs
--   </pre>
cons :: a -> DList a -> DList a
infixr 9 `cons`

-- | <b><tt>snoc xs x</tt></b> is a <a>DList</a> with the initial
--   <a>DList</a> <b><tt>xs</tt></b> and the last element
--   <b><tt>x</tt></b>.
--   
--   &lt;math&gt;(<tt>1</tt>).
--   
--   <tt>snoc</tt> obeys the law:
--   
--   <pre>
--   <a>toList</a> (<b>snoc</b> xs x) = <a>toList</a> xs <a>++</a> [x]
--   </pre>
snoc :: DList a -> a -> DList a
infixl 9 `snoc`

-- | <b><tt>append xs ys</tt></b> is a <a>DList</a> obtained from the
--   concatenation of the elements of <b><tt>xs</tt></b> and
--   <b><tt>ys</tt></b>.
--   
--   &lt;math&gt;(<tt>1</tt>).
--   
--   <tt>append</tt> obeys the law:
--   
--   <pre>
--   <a>toList</a> (<b>append</b> xs ys) = <a>toList</a> xs <a>++</a> <a>toList</a> ys
--   </pre>
append :: DList a -> DList a -> DList a

-- | <b><tt>concat xss</tt></b> is a <a>DList</a> representing the
--   concatenation of all <a>DList</a>s in the list <b><tt>xss</tt></b>.
--   
--   &lt;math&gt;(<tt><a>length</a> xss</tt>).
--   
--   <tt>concat</tt> obeys the law:
--   
--   <pre>
--   <a>toList</a> (<b>concat</b> xss) = <a>concat</a> (<a>map</a> <a>toList</a> xss)
--   </pre>
concat :: [DList a] -> DList a

-- | <b><tt>replicate n x</tt></b> is a <a>DList</a> of length
--   <b><tt>n</tt></b> with <b><tt>x</tt></b> as the value of every
--   element.
--   
--   &lt;math&gt;(<tt>n</tt>).
--   
--   <tt>replicate</tt> obeys the law:
--   
--   <pre>
--   <a>toList</a> (<b>replicate</b> n x) = <a>replicate</a> n x
--   </pre>
replicate :: Int -> a -> DList a

-- | <b><tt>head xs</tt></b> is the first element of <b><tt>xs</tt></b>. If
--   <tt>xs</tt> is empty, an <a>error</a> is raised.
--   
--   &lt;math&gt;(<tt>1</tt>).
--   
--   <tt>head</tt> obeys the law:
--   
--   <pre>
--   <b>head</b> xs = <a>head</a> (<a>toList</a> xs)
--   </pre>
head :: DList a -> a

-- | <b><tt>tail xs</tt></b> is a list of the elements in
--   <b><tt>xs</tt></b> excluding the first element. If <tt>xs</tt> is
--   empty, an <a>error</a> is raised.
--   
--   &lt;math&gt;(<tt><a>length</a> (<a>toList</a> xs)</tt>).
--   
--   <tt>tail</tt> obeys the law:
--   
--   <pre>
--   <b>tail</b> xs = <a>tail</a> (<a>toList</a> xs)
--   </pre>
tail :: DList a -> [a]

-- | <b><tt>unfoldr f z</tt></b> is the <a>DList</a> constructed from the
--   recursive application of <b><tt>f</tt></b>. The recursion starts with
--   the seed value <b><tt>z</tt></b> and ends when, for some <tt>z' :
--   b</tt>, <tt>f z' == <a>Nothing</a></tt>.
--   
--   &lt;math&gt;(<tt><a>length</a> (<a>unfoldr</a> f z)</tt>).
--   
--   <tt>unfoldr</tt> obeys the law:
--   
--   <pre>
--   <a>toList</a> (<b>unfoldr</b> f z) = <a>unfoldr</a> f z
--   </pre>
unfoldr :: (b -> Maybe (a, b)) -> b -> DList a

-- | <b><tt>foldr f z xs</tt></b> is the right-fold of <b><tt>f</tt></b>
--   over <b><tt>xs</tt></b>.
--   
--   &lt;math&gt;(<tt><a>length</a> (<a>toList</a> xs)</tt>).
--   
--   <tt>foldr</tt> obeys the law:
--   
--   <pre>
--   <b>foldr</b> f z xs = <a>foldr</a> f z (<a>toList</a> xs)
--   </pre>
foldr :: (a -> b -> b) -> b -> DList a -> b

-- | <b><tt>map f xs</tt></b> is the <a>DList</a> obtained by applying
--   <b><tt>f</tt></b> to each element of <b><tt>xs</tt></b>.
--   
--   &lt;math&gt;(<tt><a>length</a> (<a>toList</a> xs)</tt>).
--   
--   <tt>map</tt> obeys the law:
--   
--   <pre>
--   <a>toList</a> (<b>map</b> f xs) = <a>map</a> f (<a>toList</a> xs)
--   </pre>
map :: (a -> b) -> DList a -> DList b

-- | <b><tt>intercalate xs xss</tt></b> is the concatenation of
--   <b><tt>xss</tt></b> after the insertion of <b><tt>xs</tt></b> between
--   every pair of elements.
--   
--   &lt;math&gt;(<tt><a>length</a> xss</tt>).
--   
--   <tt>intercalate</tt> obeys the law:
--   
--   <pre>
--   <a>toList</a> (<b>intercalate</b> xs xss) = <a>intercalate</a> (<a>toList</a> xs) (<a>map</a> <a>toList</a> xss)
--   </pre>
intercalate :: DList a -> [DList a] -> DList a


-- | A <b>non-empty difference list</b> is a difference list paired with a
--   <a>head</a> element. Like the difference list, it supports
--   &lt;math&gt;(<tt>1</tt>) <a>append</a> and <a>snoc</a> operations.
--   
--   This module provides the type for a non-empty difference list,
--   <a>DNonEmpty</a>, and a collection of supporting functions for (a)
--   converting to and from <a>NonEmpty</a> and <a>DList</a> and (b)
--   operating efficiently on <a>DNonEmpty</a> values. The functions also
--   retain the non-strict semantics of <a>NonEmpty</a>.
module Data.DList.DNonEmpty

-- | A non-empty difference list is a pair of a <a>head</a> element and a
--   (possibly empty) difference list.
--   
--   Just as <a>DList</a> is a representation of a list, so is
--   <tt>DNonEmpty</tt> a representation of a <a>NonEmpty</a>.
--   <tt>DNonEmpty</tt> supports &lt;math&gt;(<tt>1</tt>) <a>append</a> and
--   <a>snoc</a> operations, making it useful for replacing frequent
--   applications of <a>&lt;&gt;</a> on <a>NonEmpty</a> (which is
--   implemented with <a>++</a>), especially if those uses are left-nested
--   (e.g. <tt>(a <b><a>&lt;&gt;</a></b> b) <a>&lt;&gt;</a> c</tt> ).
--   
--   Unlike <a>DList</a>, <tt>DNonEmpty</tt> is not an abstract type: its
--   constructor is exported. An alternative definition of
--   <tt>DNonEmpty</tt> is:
--   
--   <pre>
--   newtype DNonEmpty a = DNonEmpty ([a] -&gt; <a>NonEmpty</a> a)
--   </pre>
--   
--   This type would need to be abstract to avoid producing
--   <tt>DNonEmpty</tt> values that are not isomorphic to <a>NonEmpty</a>
--   values. However, this type would also require some functions (such as
--   <a>map</a>) to be implemented with <a>fromNonEmpty</a> (and thus
--   <a>++</a>), which could introduce efficiencies.
data DNonEmpty a
(:|) :: a -> DList a -> DNonEmpty a
infixr 5 :|

-- | <b><tt>fromNonEmpty xs</tt></b> is a <a>DNonEmpty</a> representing the
--   <a>NonEmpty</a> <b><tt>xs</tt></b>.
--   
--   <tt>fromNonEmpty</tt> obeys the laws:
--   
--   <pre>
--   <a>toNonEmpty</a> . <b>fromNonEmpty</b> = <a>id</a>
--   <b>fromNonEmpty</b> . <a>toNonEmpty</a> = <a>id</a>
--   </pre>
--   
--   As with <a>fromList</a>, this function is implemented with <a>++</a>.
--   Repeated uses of <tt>fromNonEmpty</tt> are just as inefficient as
--   repeated uses of <a>++</a>. If you find yourself doing some form of
--   the following (possibly indirectly), you may not be taking advantage
--   of the <a>DNonEmpty</a> representation and library:
--   
--   <pre>
--   <b>fromNonEmpty</b> . f . <a>toNonEmpty</a>
--   </pre>
--   
--   More likely, you will convert from a <a>NonEmpty</a>, perform some
--   operation on the <a>DNonEmpty</a>, and convert back to a
--   <a>NonEmpty</a>:
--   
--   <pre>
--   <a>toNonEmpty</a> . g . <b>fromNonEmpty</b>
--   </pre>
fromNonEmpty :: NonEmpty a -> DNonEmpty a

-- | <b><tt>toNonEmpty xs</tt></b> is the <a>NonEmpty</a> represented by
--   <b><tt>xs</tt></b>.
--   
--   <tt>toNonEmpty</tt> obeys the laws:
--   
--   <pre>
--   <b>toNonEmpty</b> . <a>fromNonEmpty</a> = <a>id</a>
--   <a>fromNonEmpty</a> . <b>toNonEmpty</b> = <a>id</a>
--   </pre>
--   
--   As with <a>toList</a>, evaluating <tt>toNonEmpty xs</tt> may
--   “collapse” the chain of function composition underlying many
--   <a>DList</a> functions (<a>append</a> in particular) used to construct
--   the <a>tail</a> of <tt>xs</tt>. This may affect any efficiency you
--   achieved due to laziness in the construction.
toNonEmpty :: DNonEmpty a -> NonEmpty a

-- | <b><tt>toList xs</tt></b> is the non-empty list represented by
--   <b><tt>xs</tt></b>.
--   
--   <tt>toList</tt> obeys the law:
--   
--   <pre>
--   <b>toList</b> xs = <a>toList</a> (<a>toNonEmpty</a> xs)
--   </pre>
toList :: DNonEmpty a -> [a]

-- | <b><tt>fromList xs</tt></b> is a <a>DNonEmpty</a> representing the
--   list <b><tt>xs</tt></b>. If <tt>xs</tt> is empty, an <a>error</a> is
--   raised.
--   
--   <tt>fromList</tt> obeys the law:
--   
--   <pre>
--   <b>fromList</b> xs = <a>fromNonEmpty</a> (<a>fromList</a> xs)
--   </pre>
fromList :: [a] -> DNonEmpty a

-- | <b><tt>singleton x</tt></b> is a <a>DNonEmpty</a> with the single
--   element <b><tt>x</tt></b>.
--   
--   <tt>singleton</tt> obeys the law:
--   
--   <pre>
--   <a>toNonEmpty</a> (<b>singleton</b> x) = x <a>:|</a> []
--   </pre>
singleton :: a -> DNonEmpty a

-- | <b><tt>cons x xs</tt></b> is a <a>DNonEmpty</a> with the <a>head</a>
--   <b><tt>x</tt></b> and the <a>tail</a> <b><tt>xs</tt></b>.
--   
--   &lt;math&gt;(<tt>1</tt>).
--   
--   <tt>cons</tt> obeys the law:
--   
--   <pre>
--   <a>toNonEmpty</a> (<b>cons</b> x xs) = <a>cons</a> x (<a>toNonEmpty</a> xs)
--   </pre>
cons :: a -> DNonEmpty a -> DNonEmpty a
infixr 9 `cons`

-- | <b><tt>snoc xs x</tt></b> is a <a>DNonEmpty</a> with the initial
--   <a>DNonEmpty</a> <b><tt>xs</tt></b> and the last element
--   <b><tt>x</tt></b>.
--   
--   &lt;math&gt;(<tt>1</tt>).
--   
--   <tt>snoc</tt> obeys the law:
--   
--   <pre>
--   <a>toNonEmpty</a> (<b>snoc</b> xs x) = <a>toNonEmpty</a> xs <a>&lt;&gt;</a> (x <a>:|</a> [])
--   </pre>
snoc :: DNonEmpty a -> a -> DNonEmpty a
infixl 9 `snoc`

-- | <b><tt>append xs ys</tt></b> is a <a>DNonEmpty</a> obtained from the
--   concatenation of the elements of <b><tt>xs</tt></b> and
--   <b><tt>ys</tt></b>.
--   
--   &lt;math&gt;(<tt>1</tt>).
--   
--   <tt>append</tt> obeys the law:
--   
--   <pre>
--   <a>toNonEmpty</a> (<b>append</b> xs ys) = <a>toNonEmpty</a> xs <a>&lt;&gt;</a> <a>toNonEmpty</a> ys
--   </pre>
append :: DNonEmpty a -> DNonEmpty a -> DNonEmpty a

-- | <b><tt>head xs</tt></b> is the first element of <b><tt>xs</tt></b>.
--   
--   &lt;math&gt;(<tt>1</tt>).
--   
--   <tt>head</tt> obeys the law:
--   
--   <pre>
--   <b>head</b> xs = <a>head</a> (<a>toNonEmpty</a> xs)
--   </pre>
head :: DNonEmpty a -> a

-- | <b><tt>tail xs</tt></b> is a <a>DList</a> of the elements in
--   <b><tt>xs</tt></b> excluding the first element.
--   
--   &lt;math&gt;(<tt>1</tt>).
--   
--   <tt>tail</tt> obeys the law:
--   
--   <pre>
--   <a>toList</a> (<b>tail</b> xs) = <a>tail</a> (<a>toNonEmpty</a> xs)
--   </pre>
tail :: DNonEmpty a -> DList a

-- | <b><tt>unfoldr f z</tt></b> is the <a>DNonEmpty</a> constructed from
--   the recursive application of <b><tt>f</tt></b>. The recursion starts
--   with the seed value <b><tt>z</tt></b> and ends when, for some <tt>z' :
--   b</tt>, <tt>f z' == <a>Nothing</a></tt>.
--   
--   &lt;math&gt;(<tt><a>length</a> (<a>unfoldr</a> f z)</tt>).
--   
--   <tt>unfoldr</tt> obeys the law:
--   
--   <pre>
--   <a>toNonEmpty</a> (<b>unfoldr</b> f z) = <a>unfoldr</a> f z
--   </pre>
unfoldr :: (b -> (a, Maybe b)) -> b -> DNonEmpty a

-- | <b><tt>map f xs</tt></b> is the <a>DNonEmpty</a> obtained by applying
--   <b><tt>f</tt></b> to each element of <b><tt>xs</tt></b>.
--   
--   &lt;math&gt;(<tt><a>length</a> (<a>toNonEmpty</a> xs)</tt>).
--   
--   <tt>map</tt> obeys the law:
--   
--   <pre>
--   <a>toNonEmpty</a> (<b>map</b> f xs) = <a>map</a> f (<a>toNonEmpty</a> xs)
--   </pre>
map :: (a -> b) -> DNonEmpty a -> DNonEmpty b
