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


-- | Join list - symmetric list type
--   
--   A JoinList - a list type with with cheap catenation.
--   
--   Generally speaking, joinlists have cheap construction (cons, snoc and
--   join aka. append) and expensive manipulation. For most use-cases
--   Data.Sequence is a more appropriate data structure.
--   
--   Changelog
--   
--   <ol>
--   <li>3.0 - Added views as per Data.Sequence and takes and drops.
--   Changed show instance to mimic Data.Sequence.</li>
--   <li>2.0 - more operations and some bugfixes (toList...), <tt>wrap</tt>
--   renamed to <tt>singleton</tt>.</li>
--   </ol>
@package joinlist
@version 0.3.0


-- | A "join list" datatype and operations.
--   
--   A join list is implemented a binary tree, so joining two lists
--   (catenation, aka (++)) is a cheap operation.
--   
--   This constrasts with the regular list datatype which is a cons list:
--   while consing on a regular list is by nature cheap, joining (++) is
--   expensive.
module Data.JoinList
data JoinList a
data ViewL a
EmptyL :: ViewL a
(:<) :: a -> (JoinList a) -> ViewL a
data ViewR a
EmptyR :: ViewR a
(:>) :: (JoinList a) -> a -> ViewR a

-- | Build a join list from a regular list.
fromList :: [a] -> JoinList a

-- | Convert a join list to a regular list.
toList :: JoinList a -> [a]

-- | Create an empty join list.
empty :: JoinList a

-- | Create a singleton join list.
singleton :: a -> JoinList a

-- | Cons an element to the front of the join list.
cons :: a -> JoinList a -> JoinList a

-- | Snoc an element to the tail of the join list.
snoc :: JoinList a -> a -> JoinList a

-- | Catenate two join lists. Unlike (++) on regular lists, catenation on
--   join lists is (relatively) cheap hence the name <i>join list</i>.
(++) :: JoinList a -> JoinList a -> JoinList a

-- | An alias for (++) that does not cause a name clash with the Prelude.
join :: JoinList a -> JoinList a -> JoinList a

-- | Extract the first element of a join list - i.e. the leftmost element
--   of the left spine. An error is thrown if the list is empty.
--   
--   This function performs a traversal down the left spine, so unlike
--   <tt>head</tt> on regular lists this function is not performed in
--   constant time.
head :: JoinList a -> a

-- | Extract the last element of a join list - i.e. the rightmost element
--   of the right spine. An error is thrown if the list is empty.
last :: JoinList a -> a

-- | Extract the elements after the head of a list. An error is thrown if
--   the list is empty.
tail :: JoinList a -> JoinList a

-- | Extract all the elements except the last one. An error is thrown if
--   the list is empty.
init :: JoinList a -> JoinList a

-- | Test whether a join list is empty.
null :: JoinList a -> Bool

-- | Concatenate a join list of join lists.
concat :: JoinList (JoinList a) -> JoinList a

-- | Get the length of a join list.
length :: JoinList a -> Int

-- | Map a function over a join list.
map :: (a -> b) -> JoinList a -> JoinList b
reverse :: JoinList a -> JoinList a

-- | Build a join list of n elements.
replicate :: Int -> a -> JoinList a

-- | Repeatedly build a join list by catenating the seed list.
repeated :: Int -> JoinList a -> JoinList a

-- | A generalized fold, where each constructor has an operation.
gfold :: b -> (a -> b) -> (b -> b -> b) -> JoinList a -> b

-- | Right-associative fold of a JoinList.
foldr :: (a -> b -> b) -> b -> JoinList a -> b

-- | Left-associative fold of a JoinList.
foldl :: (b -> a -> b) -> b -> JoinList a -> b

-- | unfoldl is permitted due to cheap <i>snoc-ing</i>.
unfoldl :: (b -> Maybe (a, b)) -> b -> JoinList a

-- | unfoldr - the <i>usual</i> unfoldr opertation.
unfoldr :: (b -> Maybe (a, b)) -> b -> JoinList a

-- | Access the left end of a sequence.
--   
--   Unlike the corresponing operation on Data.Sequence this is not a cheap
--   operation, the joinlist must be traversed down the left spine to find
--   the leftmost node.
--   
--   Also the traversal may involve changing the shape of the underlying
--   binary tree.
viewl :: JoinList a -> ViewL a

-- | Access the rightt end of a sequence.
--   
--   Unlike the corresponing operation on Data.Sequence this is not a cheap
--   operation, the joinlist must be traversed down the right spine to find
--   the rightmost node.
--   
--   Also the traversal may involve changing the shape of the underlying
--   binary tree.
viewr :: JoinList a -> ViewR a

-- | Take the left <tt>n</tt> elements of the list.
--   
--   Implemented with <a>viewl</a> hence the same performance caveats
--   apply.
takeLeft :: Int -> JoinList a -> JoinList a

-- | Take the right <tt>n</tt> elements of the list.
--   
--   Implemented with <a>viewr</a> hence the same performance caveats
--   apply.
takeRight :: Int -> JoinList a -> JoinList a

-- | Drop the left <tt>n</tt> elements of the list.
--   
--   Implemented with <a>viewl</a> hence the same performance caveats
--   apply.
dropLeft :: Int -> JoinList a -> JoinList a

-- | Drop the right <tt>n</tt> elements of the list.
--   
--   Implemented with <a>viewr</a> hence the same performance caveats
--   apply.
dropRight :: Int -> JoinList a -> JoinList a

-- | This function should be considered deprecated.
--   
--   <i>cross zip</i> - zip a join list against a regular list, maintaining
--   the shape of the join list provided the lengths of the lists match.
xzip :: JoinList a -> [b] -> JoinList (a, b)

-- | This function should be considered deprecated.
--   
--   Generalized cross zip - c.f. zipWith on regular lists.
xzipWith :: (a -> b -> c) -> JoinList a -> [b] -> JoinList c
instance Eq a => Eq (ViewR a)
instance Show a => Show (ViewR a)
instance Eq a => Eq (ViewL a)
instance Show a => Show (ViewL a)
instance Eq a => Eq (JoinList a)
instance Functor ViewR
instance Functor ViewL
instance Traversable JoinList
instance Foldable JoinList
instance Monad JoinList
instance Functor JoinList
instance Monoid (JoinList a)
instance Show a => Show (JoinList a)