-- 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 sequences and various sequence data structures.
@package sequence
@version 0.9.8


-- | 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
--   
--   Minimal complete defention: <a>empty</a> and <a>singleton</a> and
--   (<a>viewl</a> or <a>viewr</a>) and (<a>&gt;&lt;</a> or <a>|&gt;</a> or
--   <a>&lt;|</a>)
--   
--   Instances should satisfy the following laws:
--   
--   Monoid laws:
--   
--   <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>
--   
--   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.
class (Functor s, Foldable 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
data ViewL s c
[EmptyL] :: ViewL s c
[:<] :: c -> s c -> ViewL s c
data ViewR s c
[EmptyR] :: ViewR s c
[:>] :: s c -> c -> 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

-- | The catenable queue type. The first type argument is the type of the
--   queue we use (|&gt;)
data ToCatQueue q a
instance GHC.Base.Functor q => GHC.Base.Functor (Data.Sequence.ToCatQueue.ToCatQueue q)
instance Data.Foldable.Foldable q => Data.Foldable.Foldable (Data.Sequence.ToCatQueue.ToCatQueue q)
instance Data.SequenceClass.Sequence q => Data.SequenceClass.Sequence (Data.Sequence.ToCatQueue.ToCatQueue q)
instance Data.Traversable.Traversable q => Data.Traversable.Traversable (Data.Sequence.ToCatQueue.ToCatQueue q)


-- | A sequence, a queue, with amortized constant time: <a>|&gt;</a>, and
--   <tt>tviewl</tt>.
--   
--   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
data Queue a
instance GHC.Base.Functor Data.Sequence.Queue.Queue
instance Data.Foldable.Foldable Data.Sequence.Queue.Queue
instance Data.Traversable.Traversable Data.Sequence.Queue.Queue
instance Data.SequenceClass.Sequence Data.Sequence.Queue.Queue
instance GHC.Base.Functor Data.Sequence.Queue.B
instance Data.Foldable.Foldable Data.Sequence.Queue.B
instance Data.Traversable.Traversable Data.Sequence.Queue.B
instance GHC.Base.Functor Data.Sequence.Queue.P
instance Data.Foldable.Foldable Data.Sequence.Queue.P
instance Data.Traversable.Traversable Data.Sequence.Queue.P


-- | A sequence, a queue, with worst case constant time: <a>|&gt;</a>, and
--   <tt>tviewl</tt>.
--   
--   Based on: "Simple and Efficient Purely Functional Queues and Deques",
--   Chris Okasaki, Journal of Functional Programming 1995
module Data.Sequence.FastQueue
data FastQueue a
instance GHC.Base.Functor Data.Sequence.FastQueue.FastQueue
instance Data.Foldable.Foldable Data.Sequence.FastQueue.FastQueue
instance Data.SequenceClass.Sequence Data.Sequence.FastQueue.FastQueue
instance Data.Traversable.Traversable Data.Sequence.FastQueue.FastQueue


-- | A sequence, a catanable queue, with worst case constant time:
--   <a>&gt;&lt;</a>, <a>|&gt;</a>, <a>&lt;|</a> and <tt>tviewl</tt>.
module Data.Sequence.FastCatQueue
type FastTCQueue = ToCatQueue FastQueue


-- | A sequence, implemented as a binary tree, good performance when used
--   ephemerally
module Data.Sequence.BSeq
data BSeq a
instance GHC.Base.Functor Data.Sequence.BSeq.BSeq
instance Data.Foldable.Foldable Data.Sequence.BSeq.BSeq
instance Data.Traversable.Traversable Data.Sequence.BSeq.BSeq
instance Data.SequenceClass.Sequence Data.Sequence.BSeq.BSeq
