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


-- | A type class for sequences and various sequence data structures.
--   
--   A type class for finite sequences along with several data structures
--   that implement it.
@package sequence
@version 0.9.9.0


-- | It's safe to coerce <i>to</i> <a>Any</a> as long as you don't coerce
--   back. We define our own <a>Any</a> instead of using the one in
--   <a>GHC.Exts</a> directly to ensure that this module doesn't clash with
--   one making the opposite assumption. We use a newtype rather than a
--   closed type family with no instances because the latter weren't
--   supported until 8.0.
module Data.Sequence.FastQueue.Internal.Any
data Any

-- | Convert anything to <a>Any</a>.
toAny :: a -> Any

-- | Convert a list of anything to a list of <a>Any</a>.
toAnyList :: [a] -> [Any]


-- | A type class for sequences.
--   
--   See the package type-aligned for a generalization of this type class
--   sequences.
module Data.SequenceClass

-- | A type class for (finite) sequences
--   
--   Instances should be <i>free monoids</i> (<a>ignoring issues with
--   infinite and partially defined structures</a>), just like lists, with
--   <tt>singleton</tt> as the canonical injection and <tt>foldMap</tt>
--   factoring functions. In particular, they should satisfy the following
--   laws:
--   
--   <tt>Semigroup</tt> and <tt>Monoid</tt> laws:
--   
--   <pre>
--   (&gt;&lt;) == (Data.Semigroup.&lt;&gt;)
--   empty == mempty
--   </pre>
--   
--   In particular, this requires that
--   
--   <pre>
--   empty &gt;&lt; x == x
--   x &gt;&lt; empty == x
--   (x &gt;&lt; y) &gt;&lt; z = x &gt;&lt; (y &gt;&lt; z)
--   </pre>
--   
--   <tt>FoldMap</tt>/<tt>singleton</tt> laws:
--   
--   For any <a>Monoid</a> <tt>m</tt> and any function <tt>f :: c -&gt;
--   m</tt>,
--   
--   <ol>
--   <li><tt><a>foldMap</a> f</tt> is a monoid
--   morphism:<ul><li><pre><a>foldMap</a> f <a>mempty</a> =
--   <a>mempty</a></pre></li><li><pre><a>foldMap</a> f (m <a>&lt;&gt;</a>
--   n) = <a>foldMap</a> f m &lt;&gt; <a>foldMap</a> f
--   n</pre></li></ul></li>
--   <li><a>foldMap</a> undoes <a>singleton</a>:<pre><a>foldMap</a> f .
--   <a>singleton</a> = f</pre></li>
--   </ol>
--   
--   Observation laws:
--   
--   <pre>
--   viewl (singleton e &gt;&lt; s) == e :&lt; s
--   viewl empty == EmptyL
--   </pre>
--   
--   The behaviour of <a>&lt;|</a>,<a>|&gt;</a>, and <a>viewr</a> is
--   implied by the above laws and their default definitions.
--   
--   Warning: the default definitions are typically awful. Check them
--   carefully before relying on them. In particular, they may well work in
--   <tt>O(n^2)</tt> time (or worse?) when even definitions that convert to
--   and from lists would work in <tt>O(n)</tt> time. Exceptions: for
--   sequences with constant time concatenation, the defaults for
--   <a>&lt;|</a> and <a>|&gt;</a> are okay. For sequences with constant
--   time <a>|&gt;</a>, the default for <a>fromList</a> is okay.
class (Foldable s, Functor s) => Sequence s
empty :: Sequence s => s c
singleton :: Sequence s => c -> s c

-- | Append two sequences
(><) :: Sequence s => s c -> s c -> s c

-- | View a sequence from the left
viewl :: Sequence s => s c -> ViewL s c

-- | View a sequence from the right
--   
--   Default definition:
--   
--   <pre>
--   viewr q = case viewl q of 
--      EmptyL -&gt; EmptyR
--      h :&lt; t -&gt; case viewr t of
--          EmptyR -&gt; empty   :&gt; h
--          p :&gt; l   -&gt; (h &lt;| p) :&gt; l
--   </pre>
viewr :: Sequence s => s c -> ViewR s c

-- | Append a single element to the right
--   
--   Default definition:
--   
--   <pre>
--   l |&gt; r = l &gt;&lt; singleton r
--   </pre>
(|>) :: Sequence s => s c -> c -> s c

-- | Append a single element to the left
--   
--   Default definition:
--   
--   <pre>
--   l &lt;| r = singleton l &gt;&lt; r
--   </pre>
(<|) :: Sequence s => c -> s c -> s c

-- | Convert a list to a sequence
--   
--   Default definition:
--   
--   <pre>
--   fromList = foldl' (|&gt;) empty
--   </pre>
fromList :: Sequence s => [c] -> s c
infixr 5 <|
infixl 5 |>
infix 5 ><

-- | A view of the left end of a <a>Sequence</a>.
data ViewL s c
[EmptyL] :: ViewL s c
[:<] :: c -> s c -> ViewL s c
infixl 9 :<

-- | A view of the right end of a <a>Sequence</a>.
data ViewR s c
[EmptyR] :: ViewR s c
[:>] :: s c -> c -> ViewR s c
infixr 9 :>
instance (GHC.Show.Show c, GHC.Show.Show (s c)) => GHC.Show.Show (Data.SequenceClass.ViewL s c)
instance (GHC.Show.Show c, GHC.Show.Show (s c)) => GHC.Show.Show (Data.SequenceClass.ViewR s c)
instance Data.SequenceClass.Sequence Data.Sequence.Internal.Seq
instance Data.SequenceClass.Sequence []


-- | A purely functional catenable queue representation with that turns
--   takes a purely functional queue and turns in it into a catenable
--   queue, i.e. with the same complexity for <a>&gt;&lt;</a> as for
--   <a>|&gt;</a> Based on Purely functional data structures by Chris
--   Okasaki section 7.2: Catenable lists
module Data.Sequence.ToCatQueue.Internal

-- | The catenable queue type. The first type argument is the type of the
--   queue we use (|&gt;)
data ToCatQueue q a
[C0] :: ToCatQueue q a
[CN] :: a -> !q (ToCatQueue q a) -> ToCatQueue q a
instance GHC.Base.Functor q => GHC.Base.Functor (Data.Sequence.ToCatQueue.Internal.ToCatQueue q)
instance Data.Foldable.Foldable q => Data.Foldable.Foldable (Data.Sequence.ToCatQueue.Internal.ToCatQueue q)
instance Data.Traversable.Traversable q => Data.Traversable.Traversable (Data.Sequence.ToCatQueue.Internal.ToCatQueue q)
instance (GHC.Show.Show a, Data.Foldable.Foldable q) => GHC.Show.Show (Data.Sequence.ToCatQueue.Internal.ToCatQueue q a)
instance Data.Foldable.Foldable q => Data.Functor.Classes.Show1 (Data.Sequence.ToCatQueue.Internal.ToCatQueue q)
instance (Data.SequenceClass.Sequence q, GHC.Read.Read a) => GHC.Read.Read (Data.Sequence.ToCatQueue.Internal.ToCatQueue q a)
instance (Data.Foldable.Foldable q, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Sequence.ToCatQueue.Internal.ToCatQueue q a)
instance (Data.Foldable.Foldable q, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.Sequence.ToCatQueue.Internal.ToCatQueue q a)
instance Data.SequenceClass.Sequence q => Data.SequenceClass.Sequence (Data.Sequence.ToCatQueue.Internal.ToCatQueue q)
instance Data.SequenceClass.Sequence q => GHC.Base.Semigroup (Data.Sequence.ToCatQueue.Internal.ToCatQueue q a)
instance Data.SequenceClass.Sequence q => GHC.Base.Monoid (Data.Sequence.ToCatQueue.Internal.ToCatQueue q a)


-- | A purely functional catenable queue representation with that turns
--   takes a purely functional queue and turns in it into a catenable
--   queue, i.e. with the same complexity for <a>&gt;&lt;</a> as for
--   <a>|&gt;</a> Based on Purely functional data structures by Chris
--   Okasaki section 7.2: Catenable lists
module Data.Sequence.ToCatQueue

-- | The catenable queue type. The first type argument is the type of the
--   queue we use (|&gt;)
data ToCatQueue q a


-- | A sequence, a queue, with amortized constant time: <a>|&gt;</a>, and
--   <a>viewl</a>. It also supports <a>|&gt;</a> and <a>viewr</a> in
--   amortized logarithmic time.
--   
--   A simplified version of Okasaki's implicit recursive slowdown queues.
--   See purely functional data structures by Chris Okasaki section 8.4:
--   Queues based on implicit recursive slowdown
module Data.Sequence.Queue.Internal

-- | A queue.
data Queue a
[Q0] :: Queue a
[Q1] :: a -> Queue a
[QN] :: !B a -> Queue (P a) -> !B a -> Queue a
data P a
(:*) :: a -> a -> P a
data B a
[B1] :: a -> B a
[B2] :: !P a -> B a
instance Data.Traversable.Traversable Data.Sequence.Queue.Internal.P
instance Data.Foldable.Foldable Data.Sequence.Queue.Internal.P
instance GHC.Base.Functor Data.Sequence.Queue.Internal.P
instance GHC.Base.Functor Data.Sequence.Queue.Internal.B
instance Data.Foldable.Foldable Data.Sequence.Queue.Internal.B
instance Data.Traversable.Traversable Data.Sequence.Queue.Internal.B
instance GHC.Base.Functor Data.Sequence.Queue.Internal.Queue
instance Data.Foldable.Foldable Data.Sequence.Queue.Internal.Queue
instance Data.Traversable.Traversable Data.Sequence.Queue.Internal.Queue
instance GHC.Base.Semigroup (Data.Sequence.Queue.Internal.Queue a)
instance GHC.Base.Monoid (Data.Sequence.Queue.Internal.Queue a)
instance Data.SequenceClass.Sequence Data.Sequence.Queue.Internal.Queue
instance GHC.Show.Show a => GHC.Show.Show (Data.Sequence.Queue.Internal.Queue a)
instance Data.Functor.Classes.Show1 Data.Sequence.Queue.Internal.Queue
instance GHC.Read.Read a => GHC.Read.Read (Data.Sequence.Queue.Internal.Queue a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Sequence.Queue.Internal.Queue a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Sequence.Queue.Internal.Queue a)


-- | A sequence, a queue, with amortized constant time: <a>|&gt;</a>, and
--   <a>viewl</a>.
--   
--   A simplified version of Okasaki's implicit recursive slowdown queues.
--   See purely functional data structures by Chris Okasaki section 8.4:
--   Queues based on implicit recursive slowdown
module Data.Sequence.Queue

-- | A queue.
data Queue a


-- | A queue (actually an output-restricted deque), with worst case
--   constant time: <a>|&gt;</a>, <a>&lt;|</a>, and <a>viewl</a>. It has
--   worst case linear time <a>viewr</a>. <a>&gt;&lt;</a> is linear in the
--   length of its second argument.
--   
--   Based on: "Simple and Efficient Purely Functional Queues and Deques",
--   Chris Okasaki, Journal of Functional Programming 1995
module Data.Sequence.FastQueue.Internal

-- | A scheduled Banker's FastQueue, as described by Okasaki.
data FastQueue a
RQ :: ![a] -> !SL a -> ![Any] -> FastQueue a

-- | A lazy-spined snoc-list. Why lazy-spined? Only because that's better
--   for <a>fmap</a>. In theory, strict-spined should be a bit better for
--   everything else, but in practice it makes no measurable difference.
data SL a
SNil :: SL a
(:>) :: SL a -> a -> SL a
infixl 5 :>

-- | Append a snoc list to a list.
appendSL :: [a] -> SL a -> [a]
queue :: [a] -> SL a -> [Any] -> FastQueue a
instance GHC.Base.Functor Data.Sequence.FastQueue.Internal.SL
instance GHC.Base.Functor Data.Sequence.FastQueue.Internal.FastQueue
instance Data.SequenceClass.Sequence Data.Sequence.FastQueue.Internal.FastQueue
instance GHC.Show.Show a => GHC.Show.Show (Data.Sequence.FastQueue.Internal.FastQueue a)
instance Data.Functor.Classes.Show1 Data.Sequence.FastQueue.Internal.FastQueue
instance GHC.Read.Read a => GHC.Read.Read (Data.Sequence.FastQueue.Internal.FastQueue a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Sequence.FastQueue.Internal.FastQueue a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Sequence.FastQueue.Internal.FastQueue a)
instance Data.Foldable.Foldable Data.Sequence.FastQueue.Internal.FastQueue
instance Data.Traversable.Traversable Data.Sequence.FastQueue.Internal.FastQueue
instance GHC.Base.Semigroup (Data.Sequence.FastQueue.Internal.FastQueue a)
instance GHC.Base.Monoid (Data.Sequence.FastQueue.Internal.FastQueue a)


-- | A queue (actually an output-restricted deque), with worst case
--   constant time: <a>|&gt;</a>, <a>&lt;|</a>, and <a>viewl</a>. It has
--   worst case linear time <a>viewr</a> and <a>&gt;&lt;</a>.
--   
--   Based on: "Simple and Efficient Purely Functional Queues and Deques",
--   Chris Okasaki, Journal of Functional Programming 1995
module Data.Sequence.FastQueue

-- | A scheduled Banker's FastQueue, as described by Okasaki.
data FastQueue a


-- | A sequence, a catenable queue, with worst case constant time:
--   <a>&gt;&lt;</a>, <a>|&gt;</a>, <a>&lt;|</a> and <a>viewl</a>.
module Data.Sequence.FastCatQueue

-- | A catenable queue.
type FastTCQueue = ToCatQueue FastQueue


-- | A catenable qeueue, implemented as a binary tree, with good amortized
--   performance when used ephemerally.
module Data.Sequence.BSeq.Internal

-- | A catenable queue intended for ephemeral use.
data BSeq a
Empty :: BSeq a
Leaf :: a -> BSeq a
Node :: BSeq a -> BSeq a -> BSeq a
instance Data.Traversable.Traversable Data.Sequence.BSeq.Internal.BSeq
instance GHC.Base.Functor Data.Sequence.BSeq.Internal.BSeq
instance Data.Foldable.Foldable Data.Sequence.BSeq.Internal.BSeq
instance GHC.Base.Semigroup (Data.Sequence.BSeq.Internal.BSeq a)
instance GHC.Base.Monoid (Data.Sequence.BSeq.Internal.BSeq a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Sequence.BSeq.Internal.BSeq a)
instance Data.Functor.Classes.Show1 Data.Sequence.BSeq.Internal.BSeq
instance GHC.Read.Read a => GHC.Read.Read (Data.Sequence.BSeq.Internal.BSeq a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Sequence.BSeq.Internal.BSeq a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Sequence.BSeq.Internal.BSeq a)
instance Data.SequenceClass.Sequence Data.Sequence.BSeq.Internal.BSeq


-- | A catenable qeueue, implemented as a binary tree, with good amortized
--   performance when used ephemerally.
module Data.Sequence.BSeq

-- | A catenable queue intended for ephemeral use.
data BSeq a