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

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

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

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",
submitted to
*Journal of Functional Programming*. 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.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Deconstruction | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(1). Is this the empty 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 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

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

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

O(log(min(i,n-i))). The element at the specified position
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(log(min(i,n-i))). Update the element at the specified position
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(log(min(i,n-i))). Replace the element at the specified position
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(log(min(i,n-i))). The first i elements of a sequence.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(log(min(i,n-i))). Elements of sequence after the first i.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(log(min(i,n-i))). Split a sequence at a given position.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Lists | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(n). Create a sequence from a finite list of elements.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(n). List of elements of the sequence.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Folds | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Right associative | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(n*t). Fold over the elements of a sequence,
associating to the right.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(n*t). A variant of foldr that has no base case,
and thus may only be applied to non-empty sequences.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldr' :: (a -> b -> b) -> b -> Seq a -> b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n*t). Fold over the elements of a sequence,
associating to the right, but strictly.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldrM :: Monad m => (a -> b -> m b) -> b -> Seq a -> m b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n*t). Monadic fold over the elements of a sequence,
associating to the right, i.e. from right to left.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Left associative | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(n*t). Fold over the elements of a sequence,
associating to the left.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

O(n*t). A variant of foldl that has no base case,
and thus may only be applied to non-empty sequences.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldl' :: (a -> b -> a) -> a -> Seq b -> a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n*t). Fold over the elements of a sequence,
associating to the right, but strictly.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldlM :: Monad m => (a -> b -> m a) -> a -> Seq b -> m a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n*t). Monadic fold over the elements of a sequence,
associating to the left, i.e. from left to right.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

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

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

Produced by Haddock version 0.7 |