| EdisonCore-1.2.1: A library of efficient, purely-functional data structures (Core Implementations) | Contents | Index |
|
Data.Edison.Concrete.FingerTree | Portability | non-portable (MPTCs and functional dependencies) | Stability | internal (non-stable) | Maintainer | robdockins AT fastmail DOT fm |
|
|
|
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
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 n
referring to the length of the sequence. These bounds hold even in
a persistent (shared) setting.
|
|
Synopsis |
|
|
|
Documentation |
|
data FingerTree v a |
Finger trees with element type a, annotated with measures of type v.
The operations enforce the constraint Measured v a.
| Instances | |
|
|
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 |