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
- fromListF :: (a -> b) -> [a] -> JoinList b
- toList :: JoinList a -> [a]
- toListF :: (a -> b) -> JoinList a -> [b]
- toListM :: Monad m => (a -> m b) -> JoinList a -> m [b]
- zipWithIntoList :: (a -> b -> c) -> JoinList a -> [b] -> [c]
- empty :: JoinList a
- one :: a -> JoinList a
- cons :: a -> JoinList a -> JoinList a
- snoc :: JoinList a -> a -> JoinList a
- join :: JoinList a -> JoinList a -> JoinList a
- head :: JoinList a -> a
- takeL :: Int -> JoinList a -> JoinList a
- length :: JoinList a -> Int
- takeWhileL :: (a -> Bool) -> JoinList a -> JoinList a
- accumMapL :: (x -> st -> (y, st)) -> JoinList x -> st -> (JoinList y, st)
- null :: JoinList a -> Bool
- viewl :: JoinList a -> ViewL a
- viewr :: JoinList a -> ViewR a
- unViewL :: ViewL a -> JoinList a
- unViewR :: ViewR a -> JoinList a

# Join list datatype, opaque.

# Left view as per Data.Sequence

# Conversion between join lists and regular lists

fromList :: [a] -> JoinList aSource

Build a join list from a regular list.

This builds a tall skinny list.

WARNING - throws an error on empty list.

zipWithIntoList :: (a -> b -> c) -> JoinList a -> [b] -> [c]Source

# Construction

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

This function throws a runtime error on the empty list.

takeWhileL :: (a -> Bool) -> JoinList a -> JoinList aSource

# 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 right 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.