|
Data.Sequence | Portability | portable | Stability | experimental | Maintainer | libraries@haskell.org |
|
|
|
|
|
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 2-3 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 |
|
|
General-purpose 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,n-i))). The element at the specified position,
which should be a positive integer less than the size of the sequence.
If the position is out of range, index fails with an error.
|
|
|
O(log(min(i,n-i))). Update the element at the specified position.
If the position is out of range, the original sequence is returned.
|
|
|
O(log(min(i,n-i))). Replace the element at the specified position.
If the position is out of range, the original sequence is returned.
|
|
|
O(log(min(i,n-i))). The first i elements of a sequence.
If i is negative, take i s yields the empty sequence.
If the sequence contains fewer than i elements, the whole sequence
is returned.
|
|
|
O(log(min(i,n-i))). Elements of a sequence after the first i.
If i is negative, take i s yields the whole sequence.
If the sequence contains fewer than i elements, the empty sequence
is returned.
|
|
|
O(log(min(i,n-i))). Split a sequence at a given position.
splitAt i s = (take i s, drop i s).
|
|
Transformations
|
|
|
O(n). The reverse of a sequence.
|
|
Produced by Haddock version 0.9 |