| |||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||

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 The implementation uses 2-3 finger trees annotated with sizes, as described in section 4.2 of - Ralf Hinze and Ross Paterson,
"Finger trees: a simple general-purpose data structure",
*Journal of Functional Programming*16:2 (2006) pp 197-217. http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
| |||||||||||||||||||||||||||||||||||||||||||||||

Synopsis | |||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||

Documentation | |||||||||||||||||||||||||||||||||||||||||||||||

data Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||

Construction | |||||||||||||||||||||||||||||||||||||||||||||||

empty :: Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

O(1). The empty sequence.
| |||||||||||||||||||||||||||||||||||||||||||||||

singleton :: a -> Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

O(1). A singleton sequence.
| |||||||||||||||||||||||||||||||||||||||||||||||

(<|) :: a -> Seq a -> Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

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

(|>) :: Seq a -> a -> Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

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

(><) :: Seq a -> Seq a -> Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

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

fromList :: [a] -> Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

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 | |||||||||||||||||||||||||||||||||||||||||||||||

null :: Seq a -> Bool | |||||||||||||||||||||||||||||||||||||||||||||||

O(1). Is this the empty sequence?
| |||||||||||||||||||||||||||||||||||||||||||||||

length :: Seq a -> Int | |||||||||||||||||||||||||||||||||||||||||||||||

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

Views | |||||||||||||||||||||||||||||||||||||||||||||||

data ViewL a | |||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||

viewl :: Seq a -> ViewL a | |||||||||||||||||||||||||||||||||||||||||||||||

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

data ViewR a | |||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||

viewr :: Seq a -> ViewR a | |||||||||||||||||||||||||||||||||||||||||||||||

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

Indexing | |||||||||||||||||||||||||||||||||||||||||||||||

index :: Seq a -> Int -> a | |||||||||||||||||||||||||||||||||||||||||||||||

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.
| |||||||||||||||||||||||||||||||||||||||||||||||

adjust :: (a -> a) -> Int -> Seq a -> Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

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.
| |||||||||||||||||||||||||||||||||||||||||||||||

update :: Int -> a -> Seq a -> Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

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.
| |||||||||||||||||||||||||||||||||||||||||||||||

take :: Int -> Seq a -> Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

O(log(min(i,n-i))). The first i elements of a sequence.
If i is negative, yields the empty sequence.
If the sequence contains fewer than take i si elements, the whole sequence
is returned.
| |||||||||||||||||||||||||||||||||||||||||||||||

drop :: Int -> Seq a -> Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

O(log(min(i,n-i))). Elements of a sequence after the first i.
If i is negative, yields the whole sequence.
If the sequence contains fewer than take i si elements, the empty sequence
is returned.
| |||||||||||||||||||||||||||||||||||||||||||||||

splitAt :: Int -> Seq a -> (Seq a, Seq a) | |||||||||||||||||||||||||||||||||||||||||||||||

O(log(min(i,n-i))). Split a sequence at a given position.
.
splitAt i s = (take i s, drop i s) | |||||||||||||||||||||||||||||||||||||||||||||||

Transformations | |||||||||||||||||||||||||||||||||||||||||||||||

reverse :: Seq a -> Seq a | |||||||||||||||||||||||||||||||||||||||||||||||

O(n). The reverse of a sequence.
| |||||||||||||||||||||||||||||||||||||||||||||||

Produced by Haddock version 2.3.0 |