-- 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 difference list is an abstraction representing a list that
--   supports <math>(1) append and snoc
--   operations. This module provides the type for a difference list,
--   DList, and a collection of supporting functions for (a)
--   converting to and from lists and (b) operating on DLists
--   efficiently.
module Data.DList

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

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

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

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

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

-- | apply xs ys is the list represented by the
--   xs after appending ys to it.
--   
--   <math>(1).
--   
--   apply obeys the law:
--   
--   
--   apply xs ys = toList xs ++ ys
--   
apply :: DList a -> [a] -> [a]

-- | empty is a DList with no elements.
--   
--   empty obeys the law:
--   
--   
--   toList empty = []
--   
empty :: DList a

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

-- | cons x xs is a DList with the head
--   x and the tail xs.
--   
--   <math>(1).
--   
--   cons obeys the law:
--   
--   
--   toList (cons x xs) = x : toList xs
--   
cons :: a -> DList a -> DList a
infixr 9 `cons`

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

-- | append xs ys is a DList obtained from the
--   concatenation of the elements of xs and
--   ys.
--   
--   <math>(1).
--   
--   append obeys the law:
--   
--   
--   toList (append xs ys) = toList xs ++ toList ys
--   
append :: DList a -> DList a -> DList a

-- | concat xss is a DList representing the
--   concatenation of all DLists in the list xss.
--   
--   <math>(length xss).
--   
--   concat obeys the law:
--   
--   
--   toList (concat xss) = concat (map toList xss)
--   
concat :: [DList a] -> DList a

-- | replicate n x is a DList of length
--   n with x as the value of every
--   element.
--   
--   <math>(n).
--   
--   replicate obeys the law:
--   
--   
--   toList (replicate n x) = replicate n x
--   
replicate :: Int -> a -> DList a

-- | head xs is the first element of xs. If
--   xs is empty, an error is raised.
--   
--   <math>(1).
--   
--   head obeys the law:
--   
--   
--   head xs = head (toList xs)
--   
head :: DList a -> a

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

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

-- | foldr f z xs is the right-fold of f
--   over xs.
--   
--   <math>(length (toList xs)).
--   
--   foldr obeys the law:
--   
--   
--   foldr f z xs = foldr f z (toList xs)
--   
foldr :: (a -> b -> b) -> b -> DList a -> b

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

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

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

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

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

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

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

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

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

-- | cons x xs is a DNonEmpty with the head
--   x and the tail xs.
--   
--   <math>(1).
--   
--   cons obeys the law:
--   
--   
--   toNonEmpty (cons x xs) = cons x (toNonEmpty xs)
--   
cons :: a -> DNonEmpty a -> DNonEmpty a
infixr 9 `cons`

-- | snoc xs x is a DNonEmpty with the initial
--   DNonEmpty xs and the last element
--   x.
--   
--   <math>(1).
--   
--   snoc obeys the law:
--   
--   
--   toNonEmpty (snoc xs x) = toNonEmpty xs <> (x :| [])
--   
snoc :: DNonEmpty a -> a -> DNonEmpty a
infixl 9 `snoc`

-- | append xs ys is a DNonEmpty obtained from the
--   concatenation of the elements of xs and
--   ys.
--   
--   <math>(1).
--   
--   append obeys the law:
--   
--   
--   toNonEmpty (append xs ys) = toNonEmpty xs <> toNonEmpty ys
--   
append :: DNonEmpty a -> DNonEmpty a -> DNonEmpty a

-- | head xs is the first element of xs.
--   
--   <math>(1).
--   
--   head obeys the law:
--   
--   
--   head xs = head (toNonEmpty xs)
--   
head :: DNonEmpty a -> a

-- | tail xs is a DList of the elements in
--   xs excluding the first element.
--   
--   <math>(1).
--   
--   tail obeys the law:
--   
--   
--   toList (tail xs) = tail (toNonEmpty xs)
--   
tail :: DNonEmpty a -> DList a

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

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