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


-- | reversed lists/snoc lists
--   
--   The key idea of this library is to leverage the type system to control
--   the performance characteristics of list-manipulation code. It defines
--   the type <a>RList</a>, which is a snoc-list rather than a cons-list.
--   It also creates a symmetric module for cons-lists, which focuses on
--   the efficient and safe use of linked lists. See README.md for more
--   information.
@package reverse-list
@version 0.3.0.0


-- | This module exists primarily for symmetry with <a>Data.List.Snoc</a>
--   However, it can also be used in place of the <a>Prelude</a> list type:
--   
--   This module only exports functions that are efficient on linked lists.
--   Many functions on that type (<a>last</a>, <a>isSuffixOf</a>) though
--   technically implementable, do not represent the intended use of a
--   linked list in terms of performance.
--   
--   Additionally, this module does not export any partial functions:
--   <a>head</a> and <a>tail</a> return their results under a <a>Maybe</a>.
module Data.List.Cons

-- | As a counterpart to <a>Tsil</a>.
type List = ([])

-- | An empty <a>List</a>, such as <a>nil</a>.
pattern Nil :: List a

-- | The <a>List</a> consisting of head and tail elements, such as created
--   by <a>cons</a>.
pattern Cons :: a -> List a -> List a

-- | The empty <a>List</a>.
nil :: List a

-- | <tt>O(1)</tt> Append an element.
--   
--   If you are looking for <tt>snoc</tt>, you should use an <a>Tsil</a>,
--   or a finite sequence/queue type.
cons :: a -> List a -> List a

-- | <tt>O(1)</tt> Access the first element and trailing portion of the
--   list. See also <a>head</a> and <a>tail</a> if you only need one
--   component.
--   
--   If you are looking for <tt>unsnoc</tt>, you should use an <a>Tsil</a>,
--   or a finite sequence/queue type.
uncons :: List a -> Maybe (a, List a)

-- | Create a single-element <a>List</a>.
singleton :: a -> List a

-- | <tt>O(1)</tt> extract the first element of a list, if it exists. See
--   also <a>uncons</a> if you also need <a>tail</a> at the same time.
head :: List a -> Maybe a

-- | <tt>O(1)</tt> extract the elements of a list other than the last, if
--   they exist. See also <a>uncons</a> if you also need <a>head</a> at the
--   same time.
tail :: List a -> Maybe (List a)


-- | Useful for describing zippers and functional queues/buffers more
--   naturally and safely.
--   
--   We call it an <a>RList</a> because this is really just a vanilla list,
--   but where the semantics are that the last-added thing (internally
--   cons'ed) is understood to be at the "end" of the list.
module Data.List.Snoc

-- | This datatype defines snoc-lists: lists with O(1) append and O(n)
--   prepend. Underneath the hood, it is just a plain list, but understood
--   as containing its elements in reverse order.
--   
--   | See? It's "List" in reverse? I dunno, I just think <a>RList</a> is
--   an inelegant name, and word-initial <tt><i>t͜s</i></tt> is one of my
--   favorite phonemes.
data Tsil a

-- | I initially went with this boring name for reverse-lists. However, I
--   genuinely would rather write (and pronounce) <a>Tsil</a>.

-- | <i>Deprecated: Preferred spelling is <a>Tsil</a></i>
type RList = Tsil

-- | The empty <a>Tsil</a>.
nil :: Tsil a

-- | <tt>O(1)</tt> Append an element.
--   
--   If you are looking for <tt>cons</tt>, you should use a plain list, or
--   a finite sequence/queue type.
snoc :: Tsil a -> a -> Tsil a

-- | Create a single-element <a>Tsil</a>.
singleton :: a -> Tsil a

-- | <tt>O(1)</tt> Access the last element and initial portion of the list.
--   See also <a>last</a> and <a>init</a> if you only need one component.
--   
--   If you are looking for <tt>uncons</tt>, you should use a plain list,
--   or a finite sequence/queue type.
unsnoc :: Tsil a -> Maybe (Tsil a, a)

-- | An empty <a>RList</a>, such as <a>nil</a>.
pattern Nil :: Tsil a

-- | The <a>Tsil</a> consisting of initial and last elements, such as
--   created by <a>snoc</a>.
pattern Snoc :: Tsil a -> a -> Tsil a

-- | Test if an <a>Tsil</a> is empty.
null :: Tsil a -> Bool

-- | <tt>O(1)</tt> extract the elements of a list other than the last, if
--   they exist. See also <a>unsnoc</a> if you also need <a>last</a> at the
--   same time.
init :: Tsil a -> Maybe (Tsil a)

-- | <tt>O(1)</tt> extract the last element of a list, if it exists. See
--   also <a>unsnoc</a> if you also need <a>init</a> at the same time.
last :: Tsil a -> Maybe a

-- | Remove all <a>Nothing</a>s from an <a>Tsil</a> of <a>Maybe</a>s.
catMaybes :: Tsil (Maybe a) -> Tsil a

-- | <tt>O(n)</tt> Convert to a plain list, maintaining order.
--   
--   This is here so that you can escape back out to normal cons-list land
--   once you're done building your list.
--   
--   See <a>reverseOut</a> for when order doesn't matter.
toList :: Tsil a -> [a]

-- | <tt>O(n)</tt> Convert from a plain list, maintaining order.
--   
--   This is added for completion's sake, as I'm not sure you'll often need
--   this adapter.
--   
--   See <a>toList</a> for the inverse, or <a>reverseIn</a> for when order
--   doesn't matter.
fromList :: [a] -> Tsil a

-- | <tt>O(0)</tt> Reverse a plain cons list, rerutning an <a>Tsil</a>.
--   
--   See <a>reverseOut</a> for the inverse, and why you might use these.
reverseIn :: [a] -> Tsil a

-- | <tt>O(0)</tt> Reverse an <a>Tsil</a>, returning a plain cons list.
--   
--   This is here so that when the output list is fed to an order-agnostic
--   function, you don't have to pay the cost of reversing the
--   representation.
--   
--   See <a>toList</a> for when order matters.
reverseOut :: Tsil a -> [a]

-- | Write the contents of the <a>Tsil</a> into an array, assuming you know
--   the length of the array. This is useful in the common case of
--   buffering an unknown-length stream before allocating contiguous space
--   for the elements.
--   
--   If you sepcify to small a langth, the initial part of the array will
--   be uninitialized. If you specify to large a length, the initial part
--   of the list will not be written.
--   
--   If you are unaware of the size of the list, `Arr.fromList . fromList`
--   will do the trick, but will obviously be slower.
toArrayN :: (Contiguous arr, Element arr a) => Int -> Tsil a -> arr a

-- | Convert to a set without an intermediate conversion to a cons-list.
toSet :: Ord a => Tsil a -> Set a
instance GHC.Base.Applicative Data.List.Snoc.Tsil
instance GHC.Base.Functor Data.List.Snoc.Tsil
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.List.Snoc.Tsil a)
instance GHC.Generics.Generic (Data.List.Snoc.Tsil a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.List.Snoc.Tsil a)
instance GHC.Show.Show a => GHC.Show.Show (Data.List.Snoc.Tsil a)
instance GHC.Read.Read a => GHC.Read.Read (Data.List.Snoc.Tsil a)
instance Data.Foldable.Foldable Data.List.Snoc.Tsil
instance GHC.Base.Semigroup (Data.List.Snoc.Tsil a)
instance GHC.Base.Monoid (Data.List.Snoc.Tsil a)
instance GHC.Base.Alternative Data.List.Snoc.Tsil