Portability | to be determined. |
---|---|

Stability | highly unstable |

Maintainer | Stephen Tetley <stephen.tetley@gmail.com> |

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.