-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
@package reverse-list
@version 0.2.0
-- | This module exists primarily for symmetry with Data.List.Snoc
-- However, it can also be used in place of the Prelude list type:
--
-- This module only exports functions that are efficient on linked lists.
-- Many functions on that type (last isSuffixOf) 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:
-- head and tail return their results under a Maybe.
module Data.List.Cons
-- | As a counterpart to RList/Tsil.
type List = ([])
-- | An empty List, such as nil.
pattern Nil :: List a
-- | The List consisting of head and tail elements, such as created
-- by cons.
pattern Cons :: a -> List a -> List a
-- | The empty List.
nil :: List a
-- | O(1) Append an element.
--
-- If you are looking for snoc, you should use an
-- RList, or a finite sequence/queue type.
cons :: a -> List a -> List a
-- | O(1) Access the first element and trailing portion of the
-- list. See also head and tail if you only need one
-- component.
--
-- If you are looking for unsnoc, you should use an
-- RList, or a finite sequence/queue type.
uncons :: List a -> Maybe (a, List a)
-- | Create a single-element List.
singleton :: a -> List a
-- | O(1) extract the first element of a list, if it exists. See
-- also uncons if you also need tail at the same time.
head :: List a -> Maybe a
-- | O(1) extract the elements of a list other than the last, if
-- they exist. See also uncons if you also need head 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 RList 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.
--
-- WARNING: the Foldable instance provides a toList; this
-- simply unwraps the RList rather than reversing it. If you need
-- to convert from revered semantics to forward semantics, use this
-- module's toList.
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.
data RList a
-- | See? It's "List" in reverse? I dunno, I just think RList is an
-- inelegant name, and word-initial t͜s is one of my
-- favorite phonemes.
type Tsil = RList
-- | The empty RList.
nil :: RList a
-- | O(1) Append an element.
--
-- If you are looking for cons, you should use a plain list, or
-- a finite sequence/queue type.
snoc :: RList a -> a -> RList a
-- | Create a single-element RList.
singleton :: a -> RList a
-- | O(1) Access the last element and initial portion of the list.
-- See also last and init if you only need one component.
--
-- If you are looking for uncons, you should use a plain list,
-- or a finite sequence/queue type.
unsnoc :: RList a -> Maybe (RList a, a)
-- | An empty RList, such as nil.
pattern Nil :: RList a
-- | The RList consisting of initial and last elements, such as
-- created by snoc.
pattern Snoc :: RList a -> a -> RList a
-- | Test if an RList is empty.
null :: RList a -> Bool
-- | O(1) extract the elements of a list other than the last, if
-- they exist. See also unsnoc if you also need last at the
-- same time.
init :: RList a -> Maybe (RList a)
-- | O(1) extract the last element of a list, if it exists. See
-- also unsnoc if you also need init at the same time.
last :: RList a -> Maybe a
-- | Remove all Nothings from an RList of Maybes.
catMaybes :: RList (Maybe a) -> RList a
-- | O(n) 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 reverseOut for when order doesn't matter.
toList :: RList a -> [a]
-- | O(n) 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 toList for the inverse, or reverseIn for when order
-- doesn't matter.
fromList :: [a] -> RList a
-- | O(0) Reverse a plain cons list, rerutning an RList.
--
-- See reverseOut for the inverse, and why you might use these.
reverseIn :: [a] -> RList a
-- | O(0) Reverse an RList, 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 toList for when order matters.
reverseOut :: RList a -> [a]
-- | Write the contents of the RList 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 -> RList a -> arr a
-- | Convert to a set without an intermediate conversion to a cons-list.
toSet :: Ord a => RList a -> Set a
instance GHC.Base.Applicative Data.List.Snoc.RList
instance GHC.Base.Functor Data.List.Snoc.RList
instance GHC.Generics.Generic (Data.List.Snoc.RList a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.List.Snoc.RList a)
instance GHC.Show.Show a => GHC.Show.Show (Data.List.Snoc.RList a)
instance GHC.Read.Read a => GHC.Read.Read (Data.List.Snoc.RList a)
instance GHC.Base.Semigroup (Data.List.Snoc.RList a)
instance GHC.Base.Monoid (Data.List.Snoc.RList a)
instance GHC.Base.Alternative Data.List.Snoc.RList