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


-- | Various type-aligned sequence data structures.
--   
@package type-aligned
@version 0.9


-- | A type class for type aligned sequences: heterogeneous sequences where
--   the types enforce the element order.
--   
--   Type aligned sequences are best explained by an example: a type
--   aligned sequence of functions is a sequence f 1 , f 2 , f 3 ... f n
--   such that the composition of these functions f 1 ◦ f 2 ◦ f 3 ◦ ... ◦ f
--   n is well typed. In other words: the result type of each function in
--   the sequence must be the same as the argument type of the next
--   function (if any). In general, the elements of a type aligned sequence
--   do not have to be functions, i.e. values of type a → b, but can be
--   values of type (c a b), for some binary type constructor c. Hence, we
--   define a type aligned sequence to be a sequence of elements of the
--   type (c a_i b_i ) with the side-condition b_i−1 = a_i . If s is the
--   type of a type aligned sequence data structure, then (s c a b) is the
--   type of a type aligned sequence where the first element has type (c a
--   x), for some x, and the last element has type (c y b), for some y.
--   
--   The simplest type aligned sequence data structure is a list, see
--   <a>Data.TASequence.ConsList</a>. The other modules give various other
--   type aligned sequence data structures.
--   
--   See the paper Reflection without Remorse: Revealing a hidden sequence
--   to speed up Monadic Reflection, Atze van der Ploeg and Oleg Kiselyov,
--   Haskell Symposium 2014 for more details.
--   
--   Paper: <a>http://homepages.cwi.nl/~ploeg/zseq.pdf</a> Talk :
--   <a>http://www.youtube.com/watch?v=_XoI65Rxmss</a>
module Data.TASequence.Class

-- | minimal complete defention: <a>tempty</a> and <a>tsingleton</a> and
--   (<a>tviewl</a> or <a>tviewr</a>) and (<a>&gt;&lt;</a> or <a>|&gt;</a>
--   or <a>&lt;|</a>)
class TASequence s where l |> r = l >< tsingleton r l <| r = tsingleton l >< r l >< r = case tviewl l of { TAEmptyL -> r h :< t -> h <| (t >< r) } tviewl q = case tviewr q of { TAEmptyR -> TAEmptyL p :> l -> case tviewl p of { TAEmptyL -> l :< tempty h :< t -> h :< (t |> l) } } tviewr q = case tviewl q of { TAEmptyL -> TAEmptyR h :< t -> case tviewr t of { TAEmptyR -> tempty :> h p :> l -> (h <| p) :> l } }
tempty :: TASequence s => s c x x
tsingleton :: TASequence s => c x y -> s c x y
(><) :: TASequence s => s c x y -> s c y z -> s c x z
tviewl :: TASequence s => s c x y -> TAViewL s c x y
tviewr :: TASequence s => s c x y -> TAViewR s c x y
(|>) :: TASequence s => s c x y -> c y z -> s c x z
(<|) :: TASequence s => c x y -> s c y z -> s c x z
data TAViewL s c x y
TAEmptyL :: TAViewL s c x x
(:<) :: c x y -> s c y z -> TAViewL s c x z
data TAViewR s c x y
TAEmptyR :: TAViewR s c x x
(:>) :: s c x y -> c y z -> TAViewR s c x z
instance TASequence s => Category (s c)


-- | A type aligned sequence, a head-tail list, with worst case constant
--   time: <a>&lt;|</a>, and <a>tviewl</a>.
module Data.TASequence.ConsList
data ConsList c x y
CNil :: ConsList c x x
Cons :: c x y -> ConsList c y z -> ConsList c x z
instance TASequence ConsList


-- | 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 (&gt;<a>as for (|</a>) Based
--   on Purely functional data structures by Chris Okasaki section 7.2:
--   Catenable lists
module Data.TASequence.ToCatQueue

-- | The catenable queue type. The first type argument is the type of the
--   queue we use (|&gt;)
data ToCatQueue q c x y
instance TASequence q => TASequence (ToCatQueue q)


-- | A type aligned sequence, a snoc list, with worst case constant time:
--   <a>|&gt;</a>, and <a>tviewr</a>.
module Data.TASequence.SnocList
data SnocList c x y
SNil :: SnocList c x x
Snoc :: SnocList c x y -> c y z -> SnocList c x z
instance TASequence SnocList


-- | A type aligned sequence, a queue, with worst case constant time:
--   <a>|&gt;</a>, and <a>tviewl</a>.
--   
--   Based on: "Simple and Efficient Purely Functional Queues and Deques",
--   Chris Okasaki, Journal of Functional Programming 1995
module Data.TASequence.FastQueue
revAppend :: ConsList tc a b -> SnocList tc b d -> ConsList tc a d
rotate :: ConsList tc a b -> SnocList tc b c -> ConsList tc c d -> ConsList tc a d
data FastQueue tc a b
RQ :: !(ConsList tc a b) -> !(SnocList tc b c) -> !(ConsList tc x b) -> FastQueue tc a c
queue :: ConsList tc a b -> SnocList tc b c -> ConsList tc x b -> FastQueue tc a c
instance TASequence FastQueue


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


-- | A type aligned sequence, a catanable deque, with amortized <i>O(log
--   n)</i> case constant time: <a>&gt;&lt;</a>,<a>&lt;|</a>,|&gt;',
--   <a>tviewl</a> and <a>tviewr</a>.
--   
--   Based on: "Finger trees: a simple general-purpose data structure" Ralf
--   Hinze and Ross Paterson. in Journal of Functional Programming16:2
--   (2006), pages 197-217.
module Data.TASequence.FingerTree
data FingerTree r a b
instance TASequence FingerTree


-- | A type aligned sequence, a queue, with amortized case constant time:
--   <a>|&gt;</a>, and <a>tviewl</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.TASequence.Queue
data Queue c a b
instance TASequence Queue


-- | A type aligned sequence which uses a binary tree, where the leaves are
--   elements and then nodes are <a>&gt;&lt;</a>.
module Data.TASequence.BinaryTree
data BinaryTree c x y
instance TASequence BinaryTree