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


-- | Stacks and queues with compact representations.
--   
--   Stacks and queues 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.1.0.0

module Data.CompactSequence.Internal.Array
data Mult
Twice :: Mult -> Mult
Mul1 :: Mult
newtype Array (n :: Mult) a
Array :: SmallArray a -> Array a
newtype Size (n :: Mult)
Size :: Int -> Size
getSize :: Size n -> Int
one :: Size Mul1
twice :: Size n -> Size (Twice n)
singleton :: a -> Array Mul1 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 Mul1 a -> (# a #)
getSingletonA :: Applicative f => Array Mul1 a -> f 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
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])
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 Mult
Twice :: Mult -> Mult
Mul1 :: Mult
data Array (n :: Mult) a
data Size (n :: Mult)
getSize :: Size n -> Int
one :: Size Mul1
twice :: Size n -> Size (Twice n)
singleton :: a -> Array Mul1 a
getSingleton# :: Array Mul1 a -> (# a #)
getSingletonA :: Applicative f => Array Mul1 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])

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
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 n a -> Array n a -> ShiftedA n a
data ShiftedA n a
ShiftedA :: !Array n a -> Queue n a -> ShiftedA n a
instance Data.Traversable.Traversable (Data.CompactSequence.Queue.Internal.Queue n)
instance GHC.Base.Functor (Data.CompactSequence.Queue.Internal.Queue n)
instance Data.Traversable.Traversable (Data.CompactSequence.Queue.Internal.RD n)
instance Data.Foldable.Foldable (Data.CompactSequence.Queue.Internal.RD n)
instance GHC.Base.Functor (Data.CompactSequence.Queue.Internal.RD n)
instance Data.Traversable.Traversable (Data.CompactSequence.Queue.Internal.FD n)
instance Data.Foldable.Foldable (Data.CompactSequence.Queue.Internal.FD n)
instance GHC.Base.Functor (Data.CompactSequence.Queue.Internal.FD 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)
instance Data.Foldable.Foldable (Data.CompactSequence.Queue.Internal.Queue n)


-- | 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
data Queue a
pattern Empty :: Queue a
pattern (:<) :: a -> Queue a -> Queue a
infixr 4 :<
(|>) :: Queue a -> a -> Queue a
empty :: Queue a
snoc :: Queue a -> a -> Queue a
infixl 4 `snoc`
uncons :: Queue a -> Maybe (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
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.CompactSequence.Queue.Simple.Queue a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.CompactSequence.Queue.Simple.Queue a)
instance Data.Traversable.Traversable Data.CompactSequence.Queue.Simple.Queue
instance GHC.Base.Functor Data.CompactSequence.Queue.Simple.Queue
instance Data.Foldable.Foldable Data.CompactSequence.Queue.Simple.Queue
instance GHC.Show.Show a => GHC.Show.Show (Data.CompactSequence.Queue.Simple.Queue a)
instance GHC.Exts.IsList (Data.CompactSequence.Queue.Simple.Queue a)
instance GHC.Base.Semigroup (Data.CompactSequence.Queue.Simple.Queue a)
instance GHC.Base.Monoid (Data.CompactSequence.Queue.Simple.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
data Stack a
pattern Empty :: Stack a
pattern (:<) :: a -> Stack a -> Stack a
infixr 4 :<
empty :: Stack a
cons :: a -> Stack a -> Stack a
infixr 4 `cons`
(<|) :: a -> Stack a -> Stack a
infixr 4 <|
uncons :: Stack a -> Maybe (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.Stack a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.CompactSequence.Stack.Simple.Stack a)
instance Data.Traversable.Traversable Data.CompactSequence.Stack.Simple.Stack
instance GHC.Base.Functor Data.CompactSequence.Stack.Simple.Stack
instance Data.Foldable.Foldable Data.CompactSequence.Stack.Simple.Stack
instance GHC.Base.Semigroup (Data.CompactSequence.Stack.Simple.Stack a)
instance GHC.Base.Monoid (Data.CompactSequence.Stack.Simple.Stack a)
instance GHC.Exts.IsList (Data.CompactSequence.Stack.Simple.Stack a)
instance GHC.Show.Show a => GHC.Show.Show (Data.CompactSequence.Stack.Simple.Stack a)