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


-- | Stacks, queues, and deques with compact representations.
--   
--   Stacks, queues, and deques that take n + O(log n) space at the cost of
--   having amortized O(log n) time complexity for basic operations.
@package compact-sequences
@version 0.2.0.0

module Data.CompactSequence.Internal.Numbers
data Dyadic
DOne :: !Dyadic -> Dyadic
DTwo :: !Dyadic -> Dyadic
DEnd :: Dyadic
toDyadic :: Int -> Dyadic
data Bin23
Two23 :: !Bin23 -> Bin23
Three23 :: !Bin23 -> Bin23
End23 :: Bin23
OneEnd23 :: Bin23
toBin23 :: Int -> Bin23
data Bin45
Four45 :: !Bin45 -> Bin45
Five45 :: !Bin45 -> Bin45
End45 :: Bin45
OneEnd45 :: Bin45
TwoEnd45 :: Bin45
ThreeEnd45 :: Bin45
toBin45 :: Int -> Bin45
instance GHC.Show.Show Data.CompactSequence.Internal.Numbers.Bin23
instance GHC.Classes.Eq Data.CompactSequence.Internal.Numbers.Bin23
instance GHC.Show.Show Data.CompactSequence.Internal.Numbers.Dyadic
instance GHC.Classes.Eq Data.CompactSequence.Internal.Numbers.Dyadic


-- | Array sizes with phantom types. We use a very primitive arrangement
--   because that's all we need for now: the base type is <a>Sz1</a>,
--   <a>Sz2</a>, etc., and it's doubled as many times as necessary by
--   applying the <tt>Twice</tt> constructor. The base value is <a>sz1</a>,
--   <a>sz2</a>, etc., and it's doubled by applying the <a>twice</a>
--   function.
module Data.CompactSequence.Internal.Size
data Twice a
data Sz1
data Sz2
data Sz3
data Sz4
data Sz5
data Sz6
data Sz7
data Sz8
data Sz9
data Sz10
data Sz11
data Sz12
data Sz13
data Sz14
data Sz15
data Sz16
data Sz17
data Sz18
data Sz19
newtype Size n
Size :: Int -> Size n
getSize :: Size n -> Int
twice :: Size n -> Size (Twice n)
half :: Size (Twice m) -> Size m
one :: Size Sz1
sz1 :: Size Sz1
sz2 :: Size Sz2
sz3 :: Size Sz3
sz4 :: Size Sz4
sz5 :: Size Sz5
sz6 :: Size Sz6
sz7 :: Size Sz7
sz8 :: Size Sz8
sz9 :: Size Sz9
sz10 :: Size Sz10
sz11 :: Size Sz11
sz12 :: Size Sz12
sz13 :: Size Sz13
sz14 :: Size Sz14
sz15 :: Size Sz15
sz16 :: Size Sz16
sz17 :: Size Sz17
sz18 :: Size Sz18
sz19 :: Size Sz19

module Data.CompactSequence.Internal.Array
newtype Array n a
Array :: SmallArray a -> Array n a
singleton :: a -> Array Sz1 a

-- | Unsafely convert a <a>SmallArray</a> of size <tt>n</tt> to an
--   <tt><a>Array</a> n</tt>. This is genuinely unsafe: if <tt>n</tt> is
--   greater than the true array size, then some operation will eventually
--   violate memory safety.
unsafeSmallArrayToArray :: SmallArray a -> Array n a
arrayToSmallArray :: Array n a -> SmallArray a
getSingleton# :: Array Sz1 a -> (# a #)
getSingletonA :: Applicative f => Array Sz1 a -> f a
splitArray :: Size n -> Array (Twice n) a -> (Array n a, Array n a)
splitSmallArray# :: Int -> SmallArray a -> (# SmallArray# a, SmallArray# a #)

-- | Append two arrays of the same size. We take the size of the argument
--   arrays so we can build the result array before loading the first
--   argument array into cache. Is this the right approach? Not sure. We
--   *certainly* don't want to just use <a>&lt;&gt;</a>, because
append :: Size n -> Array n a -> Array n a -> Array (Twice n) a
appendSmallArrays :: Int -> SmallArray a -> SmallArray a -> SmallArray a
createSmallArray :: Int -> a -> (forall s. SmallMutableArray s a -> ST s ()) -> SmallArray a
arraySplitListN :: Size n -> [a] -> (Array n a, [a])
smallArraySplitListN :: Int -> [a] -> (SmallArray a, [a])
fromList :: Size n -> [a] -> Array n a
instance Data.Traversable.Traversable (Data.CompactSequence.Internal.Array.Array n)
instance Data.Foldable.Foldable (Data.CompactSequence.Internal.Array.Array n)
instance GHC.Base.Functor (Data.CompactSequence.Internal.Array.Array n)

module Data.CompactSequence.Internal.Array.Safe
data Array n a
singleton :: a -> Array Sz1 a
getSingleton# :: Array Sz1 a -> (# a #)
getSingletonA :: Applicative f => Array Sz1 a -> f a
arrayToSmallArray :: Array n a -> SmallArray a
splitArray :: Size n -> Array (Twice n) a -> (Array n a, Array n a)

-- | Append two arrays of the same size. We take the size of the argument
--   arrays so we can build the result array before loading the first
--   argument array into cache. Is this the right approach? Not sure. We
--   *certainly* don't want to just use <a>&lt;&gt;</a>, because
append :: Size n -> Array n a -> Array n a -> Array (Twice n) a
arraySplitListN :: Size n -> [a] -> (Array n a, [a])
fromList :: Size n -> [a] -> Array n a

module Data.CompactSequence.Deque.Internal
data Deque n a
Empty :: Deque n a
Shallow :: !Array n a -> Deque n a
Deep11 :: !Array n a -> !Deque (Twice n) a -> !Array n a -> Deque n a
Deep12 :: !Array n a -> !Deque (Twice n) a -> !Array n a -> !Array n a -> Deque n a
Deep13 :: !Array n a -> !Deque (Twice n) a -> !Array n a -> !Array n a -> !Array n a -> Deque n a
Deep14 :: !Array n a -> !Deque (Twice n) a -> !Array n a -> !Array n a -> !Array n a -> !Array n a -> Deque n a
Deep21 :: !Array n a -> !Array n a -> !Deque (Twice n) a -> !Array n a -> Deque n a
Deep22 :: !Array n a -> !Array n a -> Deque (Twice n) a -> !Array n a -> !Array n a -> Deque n a
Deep23 :: !Array n a -> !Array n a -> Deque (Twice n) a -> !Array n a -> !Array n a -> !Array n a -> Deque n a
Deep24 :: !Array n a -> !Array n a -> !Deque (Twice n) a -> !Array n a -> !Array n a -> !Array n a -> !Array n a -> Deque n a
Deep31 :: !Array n a -> !Array n a -> !Array n a -> !Deque (Twice n) a -> !Array n a -> Deque n a
Deep32 :: !Array n a -> !Array n a -> !Array n a -> Deque (Twice n) a -> !Array n a -> !Array n a -> Deque n a
Deep33 :: !Array n a -> !Array n a -> !Array n a -> Deque (Twice n) a -> !Array n a -> !Array n a -> !Array n a -> Deque n a
Deep34 :: !Array n a -> !Array n a -> !Array n a -> !Deque (Twice n) a -> !Array n a -> !Array n a -> !Array n a -> !Array n a -> Deque n a
Deep41 :: !Array n a -> !Array n a -> !Array n a -> !Array n a -> !Deque (Twice n) a -> !Array n a -> Deque n a
Deep42 :: !Array n a -> !Array n a -> !Array n a -> !Array n a -> !Deque (Twice n) a -> !Array n a -> !Array n a -> Deque n a
Deep43 :: !Array n a -> !Array n a -> !Array n a -> !Array n a -> !Deque (Twice n) a -> !Array n a -> !Array n a -> !Array n a -> Deque n a
Deep44 :: !Array n a -> !Array n a -> !Array n a -> !Array n a -> !Deque (Twice n) a -> !Array n a -> !Array n a -> !Array n a -> !Array n a -> Deque n a
empty :: Deque n a
consA :: Size n -> Array n a -> Deque n a -> Deque n a
snocA :: Size n -> Deque n a -> Array n a -> Deque n a
data ViewL n a
EmptyL :: ViewL n a
ConsL :: !Array n a -> Deque n a -> ViewL n a
data ViewR n a
EmptyR :: ViewR n a
SnocR :: Deque n a -> !Array n a -> ViewR n a
viewLA :: Size n -> Deque n a -> ViewL n a
viewRA :: Size n -> Deque n a -> ViewR n a
data ShiftedL n a
ShiftedL :: !Array n a -> !Array n a -> Deque (Twice n) a -> ShiftedL n a
data ShiftedR n a
ShiftedR :: Deque (Twice n) a -> !Array n a -> !Array n a -> ShiftedR n a
shiftLA :: Size n -> Deque (Twice n) a -> Array n a -> Array n a -> ShiftedL n a
shriftL :: Size n -> Array (Twice n) a -> Deque (Twice n) a -> ShiftedL n a
shiftRA :: Size n -> Array n a -> Array n a -> Deque (Twice n) a -> ShiftedR n a
shriftR :: Size n -> Array (Twice n) a -> Deque (Twice n) a -> ShiftedR n a
consSnocA :: Size n -> Array n a -> Deque n a -> Array n a -> Deque n a
data UCUS n a
EmptyUCUS :: UCUS n a
OneUCUS :: !Array n a -> UCUS n a
UCUS :: !Array n a -> Deque n a -> !Array n a -> UCUS n a
unconsUnsnocA :: Size n -> Deque n a -> UCUS n a
data Deque_ n a
Empty_ :: Deque_ n a
Shallow_ :: !Array n a -> Deque_ n a
Deep_ :: !Digit n a -> Deque (Twice n) a -> !Digit n a -> Deque_ n a
matchDeep :: Deque n a -> Deque_ n a
pattern Deep :: Digit n a -> Deque (Twice n) a -> Digit n a -> Deque n a
data Digit n a
One :: !Array n a -> Digit n a
Two :: !Array n a -> !Array n a -> Digit n a
Three :: !Array n a -> !Array n a -> !Array n a -> Digit n a
Four :: !Array n a -> !Array n a -> !Array n a -> !Array n a -> Digit n a
fromListNM :: Size sz -> Int -> State [a] (Deque sz a)
fromListNS :: Size sz -> Bin45 -> State [a] (Deque sz a)
instance Data.Traversable.Traversable (Data.CompactSequence.Deque.Internal.Deque n)
instance Data.Foldable.Foldable (Data.CompactSequence.Deque.Internal.Deque n)
instance GHC.Base.Functor (Data.CompactSequence.Deque.Internal.Deque n)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.CompactSequence.Deque.Internal.Deque n a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.CompactSequence.Deque.Internal.Deque n a)


-- | Space-efficient deques with amortized &lt;math&gt; operations. These
--   directly use an underlying array-based implementation, without doing
--   any special optimization for the first few and last few elements of
--   the deque.
module Data.CompactSequence.Deque.Simple.Internal

-- | A deque.
newtype Deque a
Deque :: Deque Sz1 a -> Deque a

-- | A bidirectional pattern synonym for the empty deque.
pattern Empty :: Deque a

-- | A bidirectional pattern synonym for manipulating the front of a deque.
pattern (:<) :: a -> Deque a -> Deque a

-- | A bidirectional pattern synonym for manipulating the rear of a deque.
pattern (:>) :: Deque a -> a -> Deque a
infixr 5 :<

-- | An infix synonym for <a>snoc</a>.
(|>) :: Deque a -> a -> Deque a
infixl 4 |>

-- | An infix synonym for <a>cons</a>.
(<|) :: a -> Deque a -> Deque a

-- | The empty deque.
empty :: Deque a

-- | Enqueue an element at the front of a deque.
cons :: a -> Deque a -> Deque a
infixr 5 `cons`

-- | Enqueue an element at the rear of a deque.
snoc :: Deque a -> a -> Deque a
infixl 4 `snoc`

-- | Dequeue an element from the front of a deque.
uncons :: Deque a -> Maybe (a, Deque a)

-- | Dequeue an element from the rear of a deque.
unsnoc :: Deque a -> Maybe (Deque a, a)

-- | &lt;math&gt;. Convert a list to a <a>Deque</a>, with the head of the
--   list at the front of the deque.
fromList :: [a] -> Deque a

-- | &lt;math&gt;. Convert a list of the given size to a <a>Deque</a>, with
--   the head of the list at the front of the deque.
fromListN :: Int -> [a] -> Deque a
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.CompactSequence.Deque.Simple.Internal.Deque a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.CompactSequence.Deque.Simple.Internal.Deque a)
instance Data.Traversable.Traversable Data.CompactSequence.Deque.Simple.Internal.Deque
instance GHC.Base.Functor Data.CompactSequence.Deque.Simple.Internal.Deque
instance Data.Foldable.Foldable Data.CompactSequence.Deque.Simple.Internal.Deque
instance GHC.Show.Show a => GHC.Show.Show (Data.CompactSequence.Deque.Simple.Internal.Deque a)
instance GHC.Exts.IsList (Data.CompactSequence.Deque.Simple.Internal.Deque a)
instance GHC.Base.Semigroup (Data.CompactSequence.Deque.Simple.Internal.Deque a)
instance GHC.Base.Monoid (Data.CompactSequence.Deque.Simple.Internal.Deque a)


-- | Space-efficient queues with amortized &lt;math&gt; operations. These
--   directly use an underlying array-based implementation, without doing
--   any special optimization for the first few and last few elements of
--   the queue.
module Data.CompactSequence.Deque.Simple

-- | A deque.
data Deque a

-- | A bidirectional pattern synonym for the empty deque.
pattern Empty :: Deque a

-- | A bidirectional pattern synonym for manipulating the front of a deque.
pattern (:<) :: a -> Deque a -> Deque a

-- | A bidirectional pattern synonym for manipulating the rear of a deque.
pattern (:>) :: Deque a -> a -> Deque a
infixr 5 :<

-- | An infix synonym for <a>snoc</a>.
(|>) :: Deque a -> a -> Deque a
infixl 4 |>

-- | The empty deque.
empty :: Deque a

-- | Enqueue an element at the front of a deque.
cons :: a -> Deque a -> Deque a
infixr 5 `cons`

-- | Enqueue an element at the rear of a deque.
snoc :: Deque a -> a -> Deque a
infixl 4 `snoc`

-- | Dequeue an element from the front of a deque.
uncons :: Deque a -> Maybe (a, Deque a)

-- | Dequeue an element from the rear of a deque.
unsnoc :: Deque a -> Maybe (Deque a, a)

-- | &lt;math&gt;. Convert a list to a <a>Deque</a>, with the head of the
--   list at the front of the deque.
fromList :: [a] -> Deque a

-- | &lt;math&gt;. Convert a list of the given size to a <a>Deque</a>, with
--   the head of the list at the front of the deque.
fromListN :: Int -> [a] -> Deque a

module Data.CompactSequence.Queue.Internal
data FD n a
FD1 :: !Array n a -> FD n a
FD2 :: !Array n a -> !Array n a -> FD n a
FD3 :: !Array n a -> !Array n a -> !Array n a -> FD n a
data RD n a
RD0 :: RD n a
RD1 :: !Array n a -> RD n a
RD2 :: !Array n a -> !Array n a -> RD n a
data Queue n a
Empty :: Queue n a
Node10 :: !Array n a -> !Queue (Twice n) a -> Queue n a
Node11 :: !Array n a -> !Queue (Twice n) a -> !Array n a -> Queue n a
Node12 :: !Array n a -> !Queue (Twice n) a -> !Array n a -> !Array n a -> Queue n a
Node20 :: !Array n a -> !Array n a -> Queue (Twice n) a -> Queue n a
Node21 :: !Array n a -> !Array n a -> Queue (Twice n) a -> !Array n a -> Queue n a
Node22 :: !Array n a -> !Array n a -> !Queue (Twice n) a -> !Array n a -> !Array n a -> Queue n a
Node30 :: !Array n a -> !Array n a -> !Array n a -> Queue (Twice n) a -> Queue n a
Node31 :: !Array n a -> !Array n a -> !Array n a -> Queue (Twice n) a -> !Array n a -> Queue n a
Node32 :: !Array n a -> !Array n a -> !Array n a -> !Queue (Twice n) a -> !Array n a -> !Array n a -> Queue n a
data Queue_ n a
Empty_ :: Queue_ n a
Node_ :: !FD n a -> Queue (Twice n) a -> !RD n a -> Queue_ n a
matchNode :: Queue n a -> Queue_ n a
pattern Node :: FD n a -> Queue (Twice n) a -> RD n a -> Queue n a
data ViewA n a
EmptyA :: ViewA n a
ConsA :: !Array n a -> Queue n a -> ViewA n a
data ViewA2 n a
EmptyA2 :: ViewA2 n a
ConsA2 :: !Array n a -> !Array n a -> Queue n a -> ViewA2 n a
singletonA :: Array n a -> Queue n a
viewA :: Size n -> Queue n a -> ViewA n a
empty :: Queue n a
snocA :: Size n -> Queue n a -> Array n a -> Queue n a

-- | Uncons from a node and snoc onto it. Ensure that if the operation is
--   expensive then it leaves the node in a safe configuration. Why do we
--   need this? Suppose we have
--   
--   Two m Two
--   
--   If we snoc onto this, the operation cascades, and we get
--   
--   Two m Zero
--   
--   Then when we view, we get
--   
--   One m Zero
--   
--   which is not safe.
--   
--   Instead, we need to view first, getting
--   
--   One m Two
--   
--   immediately, then snoc on, cascading and getting
--   
--   Three m Zero
--   
--   which is safe.
--   
--   If instead we have
--   
--   One m One
--   
--   we have to do the opposite: snoc then view. We might as well just
--   write a dedicated shifting operation.
shiftA :: Size n -> Queue (Twice n) a -> Array n a -> Array n a -> ShiftedA n a
shrift :: Size n -> Array (Twice n) a -> Queue (Twice n) a -> ShiftedA n a
data ShiftedA n a
ShiftedA :: !Array n a -> !Array n a -> Queue (Twice n) a -> ShiftedA n a
instance Data.Traversable.Traversable (Data.CompactSequence.Queue.Internal.Queue n)
instance Data.Foldable.Foldable (Data.CompactSequence.Queue.Internal.Queue n)
instance GHC.Base.Functor (Data.CompactSequence.Queue.Internal.Queue n)
instance GHC.Show.Show a => GHC.Show.Show (Data.CompactSequence.Queue.Internal.Queue n a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.CompactSequence.Queue.Internal.Queue n a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.CompactSequence.Queue.Internal.Queue n a)


-- | Space-efficient queues with amortized &lt;math&gt; operations. These
--   directly use an underlying array-based implementation, without doing
--   any special optimization for the first few and last few elements of
--   the queue.
module Data.CompactSequence.Queue.Simple.Internal

-- | A queue.
newtype Queue a
Queue :: Queue Sz1 a -> Queue a

-- | A bidirectional pattern synonym for the empty queue.
pattern Empty :: Queue a

-- | A unidirectional pattern synonym for viewing the front of a queue.
pattern (:<) :: a -> Queue a -> Queue a
infixr 5 :<

-- | An infix synonym for <a>snoc</a>.
(|>) :: Queue a -> a -> Queue a
infixl 4 |>

-- | The empty queue.
empty :: Queue a

-- | Enqueue an element at the rear of a queue.
snoc :: Queue a -> a -> Queue a
infixl 4 `snoc`

-- | Dequeue an element from the front of a queue.
uncons :: Queue a -> Maybe (a, Queue a)

-- | Take up to the given number of elements from the front of a queue to
--   form a new queue. &lt;math&gt;, where &lt;math&gt; is the integer
--   argument and &lt;math&gt; is the size of the queue.
take :: Int -> Queue a -> Queue a

-- | &lt;math&gt;. Convert a list to a <a>Queue</a>, with the head of the
--   list at the front of the queue.
fromList :: [a] -> Queue a

-- | &lt;math&gt;. Convert a list of the given size to a <a>Queue</a>, with
--   the head of the list at the front of the queue.
fromListN :: Int -> [a] -> Queue a

-- | &lt;math&gt;. Convert a list of the given size to a <a>Queue</a>, with
--   the head of the list at the front of the queue. Unlike
--   <a>fromListN</a>, the conversion is performed incrementally. This is
--   generally beneficial if the list is represented compactly (e.g., an
--   enumeration) or when it's otherwise not important to consume the
--   entire list immediately.
fromListNIncremental :: Int -> [a] -> Queue a
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.CompactSequence.Queue.Simple.Internal.Queue a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.CompactSequence.Queue.Simple.Internal.Queue a)
instance Data.Traversable.Traversable Data.CompactSequence.Queue.Simple.Internal.Queue
instance GHC.Base.Functor Data.CompactSequence.Queue.Simple.Internal.Queue
instance Data.Foldable.Foldable Data.CompactSequence.Queue.Simple.Internal.Queue
instance GHC.Show.Show a => GHC.Show.Show (Data.CompactSequence.Queue.Simple.Internal.Queue a)
instance GHC.Exts.IsList (Data.CompactSequence.Queue.Simple.Internal.Queue a)
instance GHC.Base.Semigroup (Data.CompactSequence.Queue.Simple.Internal.Queue a)
instance GHC.Base.Monoid (Data.CompactSequence.Queue.Simple.Internal.Queue a)


-- | Space-efficient queues with amortized &lt;math&gt; operations. These
--   directly use an underlying array-based implementation, without doing
--   any special optimization for the first few and last few elements of
--   the queue.
module Data.CompactSequence.Queue.Simple

-- | A queue.
data Queue a

-- | A bidirectional pattern synonym for the empty queue.
pattern Empty :: Queue a

-- | A unidirectional pattern synonym for viewing the front of a queue.
pattern (:<) :: a -> Queue a -> Queue a
infixr 5 :<

-- | An infix synonym for <a>snoc</a>.
(|>) :: Queue a -> a -> Queue a
infixl 4 |>

-- | The empty queue.
empty :: Queue a

-- | Enqueue an element at the rear of a queue.
snoc :: Queue a -> a -> Queue a
infixl 4 `snoc`

-- | Dequeue an element from the front of a queue.
uncons :: Queue a -> Maybe (a, Queue a)

-- | Take up to the given number of elements from the front of a queue to
--   form a new queue. &lt;math&gt;, where &lt;math&gt; is the integer
--   argument and &lt;math&gt; is the size of the queue.
take :: Int -> Queue a -> Queue a

-- | &lt;math&gt;. Convert a list to a <a>Queue</a>, with the head of the
--   list at the front of the queue.
fromList :: [a] -> Queue a

-- | &lt;math&gt;. Convert a list of the given size to a <a>Queue</a>, with
--   the head of the list at the front of the queue.
fromListN :: Int -> [a] -> Queue a

-- | &lt;math&gt;. Convert a list of the given size to a <a>Queue</a>, with
--   the head of the list at the front of the queue. Unlike
--   <a>fromListN</a>, the conversion is performed incrementally. This is
--   generally beneficial if the list is represented compactly (e.g., an
--   enumeration) or when it's otherwise not important to consume the
--   entire list immediately.
fromListNIncremental :: Int -> [a] -> Queue a

module Data.CompactSequence.Stack.Internal
data Stack n a
Empty :: Stack n a
One :: !Array n a -> !Stack (Twice n) a -> Stack n a
Two :: !Array n a -> !Array n a -> Stack (Twice n) a -> Stack n a
Three :: !Array n a -> !Array n a -> !Array n a -> !Stack (Twice n) a -> Stack n a
empty :: Stack n a
consA :: Size n -> Array n a -> Stack n a -> Stack n a
data ViewA n a
EmptyA :: ViewA n a
ConsA :: !Array n a -> Stack n a -> ViewA n a
unconsA :: Size n -> Stack n a -> ViewA n a
instance Data.Traversable.Traversable (Data.CompactSequence.Stack.Internal.Stack n)
instance GHC.Base.Functor (Data.CompactSequence.Stack.Internal.Stack n)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.CompactSequence.Stack.Internal.Stack n a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.CompactSequence.Stack.Internal.Stack n a)
instance GHC.Show.Show a => GHC.Show.Show (Data.CompactSequence.Stack.Internal.Stack n a)
instance Data.Foldable.Foldable (Data.CompactSequence.Stack.Internal.Stack n)


-- | Space-efficient stacks with amortized &lt;math&gt; operations. These
--   directly use an underlying array-based implementation, without doing
--   any special optimization for the very top of the stack.
module Data.CompactSequence.Stack.Simple.Internal

-- | A stack.
newtype Stack a
Stack :: Stack Sz1 a -> Stack a
[unStack] :: Stack a -> Stack Sz1 a

-- | A bidirectional pattern synonym for the empty stack.
pattern Empty :: Stack a

-- | A bidirectional pattern synonym for working with the front of a stack.
pattern (:<) :: a -> Stack a -> Stack a
infixr 5 :<

-- | The empty stack.
empty :: Stack a

-- | Push an element onto the front of a stack.
--   
--   &lt;math&gt;
cons :: a -> Stack a -> Stack a
infixr 5 `cons`

-- | An infix synonym for <a>cons</a>.
(<|) :: a -> Stack a -> Stack a
infixr 5 <|

-- | Pop an element off the front of a stack.
--   
--   Accessing the first element is &lt;math&gt;. Accessing the rest is
--   &lt;math&gt;.
uncons :: Stack a -> Maybe (a, Stack a)

-- | &lt;math&gt;. Compare an <a>Int</a> to the length of a <a>Stack</a>.
--   
--   <pre>
--   compareLength n xs = compare n (length xs)
--   </pre>
compareLength :: Int -> Stack a -> Ordering

-- | Take up to the given number of elements from the front of a stack to
--   form a new stack. &lt;math&gt;, where &lt;math&gt; is the integer
--   argument and &lt;math&gt; is the size of the stack.
take :: Int -> Stack a -> Stack a

-- | &lt;math&gt;. Convert a list to a stack, with the first element of the
--   list as the top of the stack.
fromList :: [a] -> Stack a

-- | &lt;math&gt;. Convert a list of known length to a stack, with the
--   first element of the list as the top of the stack.
fromListN :: Int -> [a] -> Stack a
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.CompactSequence.Stack.Simple.Internal.Stack a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.CompactSequence.Stack.Simple.Internal.Stack a)
instance Data.Traversable.Traversable Data.CompactSequence.Stack.Simple.Internal.Stack
instance GHC.Base.Functor Data.CompactSequence.Stack.Simple.Internal.Stack
instance Data.Foldable.Foldable Data.CompactSequence.Stack.Simple.Internal.Stack
instance GHC.Base.Semigroup (Data.CompactSequence.Stack.Simple.Internal.Stack a)
instance GHC.Base.Monoid (Data.CompactSequence.Stack.Simple.Internal.Stack a)
instance GHC.Exts.IsList (Data.CompactSequence.Stack.Simple.Internal.Stack a)
instance GHC.Show.Show a => GHC.Show.Show (Data.CompactSequence.Stack.Simple.Internal.Stack a)


-- | Space-efficient stacks with amortized &lt;math&gt; operations. These
--   directly use an underlying array-based implementation, without doing
--   any special optimization for the very top of the stack.
module Data.CompactSequence.Stack.Simple

-- | A stack.
data Stack a

-- | A bidirectional pattern synonym for the empty stack.
pattern Empty :: Stack a

-- | A bidirectional pattern synonym for working with the front of a stack.
pattern (:<) :: a -> Stack a -> Stack a
infixr 5 :<

-- | The empty stack.
empty :: Stack a

-- | Push an element onto the front of a stack.
--   
--   &lt;math&gt;
cons :: a -> Stack a -> Stack a
infixr 5 `cons`

-- | An infix synonym for <a>cons</a>.
(<|) :: a -> Stack a -> Stack a
infixr 5 <|

-- | Pop an element off the front of a stack.
--   
--   Accessing the first element is &lt;math&gt;. Accessing the rest is
--   &lt;math&gt;.
uncons :: Stack a -> Maybe (a, Stack a)

-- | &lt;math&gt;. Compare an <a>Int</a> to the length of a <a>Stack</a>.
--   
--   <pre>
--   compareLength n xs = compare n (length xs)
--   </pre>
compareLength :: Int -> Stack a -> Ordering

-- | Take up to the given number of elements from the front of a stack to
--   form a new stack. &lt;math&gt;, where &lt;math&gt; is the integer
--   argument and &lt;math&gt; is the size of the stack.
take :: Int -> Stack a -> Stack a

-- | &lt;math&gt;. Convert a list to a stack, with the first element of the
--   list as the top of the stack.
fromList :: [a] -> Stack a

-- | &lt;math&gt;. Convert a list of known length to a stack, with the
--   first element of the list as the top of the stack.
fromListN :: Int -> [a] -> Stack a