|EdisonCore-220.127.116.11: A library of efficent, purely-functional data structures (Core Implementations)||Source code||Contents||Index|
|Portability||non-portable (MPTCs and functional dependencies)|
|Maintainer||robdockins AT fastmail DOT fm|
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.
|Finger trees with element type a, annotated with measures of type v.
The operations enforce the constraint Measured v a.
|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|