
Data.Sequence  Portability  portable  Stability  experimental  Maintainer  ross@soi.city.ac.uk 





Description 
General purpose finite sequences.
Apart from being finite and having strict operations, sequences
also differ from lists in supporting a wider variety of operations
efficiently.
An amortized running time is given for each operation, with n referring
to the length of the sequence and i being the integral index used by
some operations. These bounds hold even in a persistent (shared) setting.
The implementation uses 23 finger trees annotated with sizes,
as described in section 4.2 of
Note: Many of these operations have the same names as similar
operations on lists in the Prelude. The ambiguity may be resolved
using either qualification or the hiding clause.


Synopsis 



Documentation 


Generalpurpose finite sequences.
 Instances  


Construction



O(1). The empty sequence.



O(1). A singleton sequence.



O(1). Add an element to the left end of a sequence.
Mnemonic: a triangle with the single element at the pointy end.



O(1). Add an element to the right end of a sequence.
Mnemonic: a triangle with the single element at the pointy end.



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



O(n). Create a sequence from a finite list of elements.
There is a function toList in the opposite direction for all
instances of the Foldable class, including Seq.


Deconstruction


Additional functions for deconstructing sequences are available
via the Foldable instance of Seq.


Queries



O(1). Is this the empty sequence?



O(1). The number of elements in the sequence.


Views



View of the left end of a sequence.
 Constructors  EmptyL  empty sequence
 (:<) a (Seq a)  leftmost element and the rest of the sequence

 Instances  



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



View of the right end of a sequence.
 Constructors  EmptyR  empty sequence
 (:>) (Seq a) a  the sequence minus the rightmost element,
and the rightmost element

 Instances  



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


Indexing



O(log(min(i,ni))). The element at the specified position



O(log(min(i,ni))). Update the element at the specified position



O(log(min(i,ni))). Replace the element at the specified position



O(log(min(i,ni))). The first i elements of a sequence.



O(log(min(i,ni))). Elements of a sequence after the first i.



O(log(min(i,ni))). Split a sequence at a given position.


Transformations



O(n). The reverse of a sequence.


Produced by Haddock version 0.8 