| ||||||||

| ||||||||

Description | ||||||||

A general sequence representation with arbitrary annotations, for use as a base for implementations of various collection types, as described in section 4 of - Ralf Hinze and Ross Paterson,
"Finger trees: a simple general-purpose data structure",
*Journal of Functional Programming*16:2 (2006) pp 197-217. http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
This data structure forms the basis of the Data.Edison.Seq.FingerSeq sequence data structure. An amortized running time is given for each operation, with | ||||||||

Synopsis | ||||||||

Documentation | ||||||||

data FingerTree v a | ||||||||

| ||||||||

data Split t a | ||||||||

| ||||||||

empty :: Measured v a => FingerTree v a | ||||||||

O(1). The empty sequence.
| ||||||||

singleton :: Measured v a => a -> FingerTree v a | ||||||||

O(1). A singleton sequence.
| ||||||||

lcons :: Measured v a => a -> FingerTree v a -> FingerTree v a | ||||||||

O(1). Add an element to the left end of a sequence.
| ||||||||

rcons :: Measured v a => a -> FingerTree v a -> FingerTree v a | ||||||||

O(1). Add an element to the right end of a sequence.
| ||||||||

append :: Measured v a => FingerTree v a -> FingerTree v a -> FingerTree v a | ||||||||

O(log(min(n1,n2))). Concatenate two sequences.
| ||||||||

fromList :: Measured v a => [a] -> FingerTree v a | ||||||||

O(n). Create a sequence from a finite list of elements.
| ||||||||

toList :: FingerTree v a -> [a] | ||||||||

null :: Measured v a => FingerTree v a -> Bool | ||||||||

O(1). Is this the empty sequence?
| ||||||||

size :: FingerTree v a -> Int | ||||||||

lview :: (Measured v a, Monad m) => FingerTree v a -> m (a, FingerTree v a) | ||||||||

O(1). Analyse the left end of a sequence.
| ||||||||

rview :: (Measured v a, Monad m) => FingerTree v a -> m (a, FingerTree v a) | ||||||||

O(1). Analyse the right end of a sequence.
| ||||||||

split :: Measured v a => (v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a) | ||||||||

O(log(min(i,n-i))). Split a sequence at a point where the predicate
on the accumulated measure changes from False to True.
| ||||||||

takeUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a | ||||||||

dropUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a | ||||||||

splitTree :: Measured v a => (v -> Bool) -> v -> FingerTree v a -> Split (FingerTree v a) a | ||||||||

reverse :: Measured v a => FingerTree v a -> FingerTree v a | ||||||||

O(n). The reverse of a sequence.
| ||||||||

mapTree :: Measured v2 a2 => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 | ||||||||

foldFT :: b -> (b -> b -> b) -> (a -> b) -> FingerTree v a -> b | ||||||||

reduce1 :: (a -> a -> a) -> FingerTree v a -> a | ||||||||

reduce1' :: (a -> a -> a) -> FingerTree v a -> a | ||||||||

strict :: FingerTree v a -> FingerTree v a | ||||||||

strictWith :: (a -> b) -> FingerTree v a -> FingerTree v a | ||||||||

structuralInvariant :: (Eq v, Measured v a) => FingerTree v a -> Bool | ||||||||

Produced by Haddock version 0.8 |