wumpus-basic-0.15.0: Basic objects and system code built on Wumpus-Core.

Wumpus.Basic.Utils.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.

Synopsis

Join list datatype, opaque.

Left view as per Data.Sequence

data ViewL a Source

Constructors

EmptyL 
a :< (JoinList a) 

Instances

Functor ViewL 
Eq a => Eq (ViewL a) 
Show a => Show (ViewL a) 

data ViewR a Source

Constructors

EmptyR 
(JoinList a) :> a 

Instances

Functor ViewR 
Eq a => Eq (ViewR a) 
Show a => Show (ViewR a) 

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.

fromListF :: (a -> b) -> [a] -> JoinList bSource

toList :: JoinList a -> [a]Source

Convert a join list to a regular list.

toListF :: (a -> b) -> JoinList a -> [b]Source

toListM :: Monad m => (a -> m b) -> JoinList a -> m [b]Source

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

Construction

empty :: JoinList aSource

Create an empty join list.

one :: a -> JoinList aSource

Create a singleton join list.

cons :: a -> JoinList a -> JoinList aSource

Cons an element to the front of the join list.

snoc :: JoinList a -> a -> JoinList aSource

Snoc an element to the tail of the join list.

Basic functions

head :: JoinList a -> aSource

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.

accumMapL :: (x -> st -> (y, st)) -> JoinList x -> st -> (JoinList y, st)Source

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.