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


-- | A type class for sequences and various sequence data structures.
--   
@package sequence
@version 0.9.6


-- | 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 where l |> r = l >< singleton r l <| r = singleton l >< r l >< r = case viewl l of { EmptyL -> r h :< t -> h <| (t >< r) } viewl q = case viewr q of { EmptyR -> EmptyL p :> l -> case viewl p of { EmptyL -> l :< empty h :< t -> h :< (t |> l) } } viewr q = case viewl q of { EmptyL -> EmptyR h :< t -> case viewr t of { EmptyR -> empty :> h p :> l -> (h <| p) :> l } }
empty :: Sequence s => s c
singleton :: Sequence s => c -> s c
(><) :: Sequence s => s c -> s c -> s c
viewl :: Sequence s => s c -> ViewL s c
viewr :: Sequence s => s c -> ViewR s c
(|>) :: Sequence s => s c -> c -> s c
(<|) :: 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 Sequence []
instance Sequence Seq


-- | 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 Sequence Queue
instance Traversable Queue
instance Foldable Queue
instance Functor Queue
instance Traversable B
instance Foldable B
instance Functor B
instance Traversable P
instance Foldable P
instance Functor 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 Traversable FastQueue
instance Sequence FastQueue
instance Foldable FastQueue
instance Functor FastQueue


-- | 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 Traversable q => Traversable (ToCatQueue q)
instance Sequence q => Sequence (ToCatQueue q)
instance Foldable q => Foldable (ToCatQueue q)
instance Functor q => Functor (ToCatQueue q)


-- | 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