| Portability | to be determined. |
|---|---|
| Stability | highly unstable |
| Maintainer | Stephen Tetley <stephen.tetley@gmail.com> |
Data.JoinList
Contents
Description
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.
- data JoinList a
- data ViewL a
- data ViewR a
- fromList :: [a] -> JoinList a
- toList :: JoinList a -> [a]
- empty :: JoinList a
- singleton :: a -> JoinList a
- cons :: a -> JoinList a -> JoinList a
- snoc :: JoinList a -> a -> JoinList a
- (++) :: JoinList a -> JoinList a -> JoinList a
- join :: JoinList a -> JoinList a -> JoinList a
- head :: JoinList a -> a
- last :: JoinList a -> a
- tail :: JoinList a -> JoinList a
- init :: JoinList a -> JoinList a
- null :: JoinList a -> Bool
- concat :: JoinList (JoinList a) -> JoinList a
- length :: JoinList a -> Int
- map :: (a -> b) -> JoinList a -> JoinList b
- reverse :: JoinList a -> JoinList a
- replicate :: Int -> a -> JoinList a
- repeated :: Int -> JoinList a -> JoinList a
- gfold :: b -> (a -> b) -> (b -> b -> b) -> JoinList a -> b
- foldr :: (a -> b -> b) -> b -> JoinList a -> b
- foldl :: (b -> a -> b) -> b -> JoinList a -> b
- unfoldl :: (b -> Maybe (a, b)) -> b -> JoinList a
- unfoldr :: (b -> Maybe (a, b)) -> b -> JoinList a
- viewl :: JoinList a -> ViewL a
- viewr :: JoinList a -> ViewR a
- takeLeft :: Int -> JoinList a -> JoinList a
- takeRight :: Int -> JoinList a -> JoinList a
- dropLeft :: Int -> JoinList a -> JoinList a
- dropRight :: Int -> JoinList a -> JoinList a
- xzip :: JoinList a -> [b] -> JoinList (a, b)
- xzipWith :: (a -> b -> c) -> JoinList a -> [b] -> JoinList c
Join list datatype, opaque.
Views as per Data.Sequence
Conversion between join lists and regular lists
Construction
(++) :: JoinList a -> JoinList a -> JoinList aSource
Catenate two join lists. Unlike (++) on regular lists, catenation on join lists is (relatively) cheap hence the name join list.
join :: JoinList a -> JoinList a -> JoinList aSource
An alias for (++) that does not cause a name clash with the Prelude.
Basic functions
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 head on regular lists this function is not performed
in constant time.
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.
tail :: JoinList a -> JoinList aSource
Extract the elements after the head of a list. An error is thrown if the list is empty.
init :: JoinList a -> JoinList aSource
Extract all the elements except the last one. An error is thrown if the list is empty.
Building join lists
repeated :: Int -> JoinList a -> JoinList aSource
Repeatedly build a join list by catenating the seed list.
Folds and unfolds
gfold :: b -> (a -> b) -> (b -> b -> b) -> JoinList a -> bSource
A generalized fold, where each constructor has an operation.
Views
viewl :: JoinList a -> ViewL aSource
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.
viewr :: JoinList a -> ViewR aSource
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.
Sublists
takeLeft :: Int -> JoinList a -> JoinList aSource
Take the left n elements of the list.
Implemented with viewl hence the same performance caveats
apply.
takeRight :: Int -> JoinList a -> JoinList aSource
Take the right n elements of the list.
Implemented with viewr hence the same performance caveats
apply.
dropLeft :: Int -> JoinList a -> JoinList aSource
Drop the left n elements of the list.
Implemented with viewl hence the same performance caveats
apply.
dropRight :: Int -> JoinList a -> JoinList aSource
Drop the right n elements of the list.
Implemented with viewr hence the same performance caveats
apply.