| EdisonCore-1.2.1.2: A library of efficent, purely-functional data structures (Core Implementations) | Source code | 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 |
|
|
Finger trees with element type a, annotated with measures of type v.
The operations enforce the constraint Measured v a.
| Instances | |
|
|
|
|
|
|
O(1). The empty sequence.
|
|
|
O(1). A singleton sequence.
|
|
|
O(1). Add an element to the left end of a sequence.
|
|
|
O(1). Add an element to the right end of a sequence.
|
|
|
O(log(min(n1,n2))). Concatenate two sequences.
|
|
|
O(n). Create a sequence from a finite list of elements.
|
|
|
|
|
O(1). Is this the empty sequence?
|
|
|
|
|
O(1). Analyse the left end of a sequence.
|
|
|
O(1). Analyse the right end of a sequence.
|
|
|
O(log(min(i,n-i))). Split a sequence at a point where the predicate
on the accumulated measure changes from False to True.
|
|
|
|
|
|
|
|
|
O(n). The reverse of a sequence.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Produced by Haddock version 2.3.0 |