Portability | portable |
---|---|

Stability | experimental |

Maintainer | ross@soi.city.ac.uk |

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

- 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

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

- data Seq a
- empty :: Seq a
- singleton :: a -> Seq a
- (<|) :: a -> Seq a -> Seq a
- (|>) :: Seq a -> a -> Seq a
- (><) :: Seq a -> Seq a -> Seq a
- fromList :: [a] -> Seq a
- null :: Seq a -> Bool
- length :: Seq a -> Int
- data ViewL a
- viewl :: Seq a -> ViewL a
- data ViewR a
- viewr :: Seq a -> ViewR a
- index :: Seq a -> Int -> a
- adjust :: (a -> a) -> Int -> Seq a -> Seq a
- update :: Int -> a -> Seq a -> Seq a
- take :: Int -> Seq a -> Seq a
- drop :: Int -> Seq a -> Seq a
- splitAt :: Int -> Seq a -> (Seq a, Seq a)
- reverse :: Seq a -> Seq a

# Documentation

General-purpose finite sequences.

# Construction

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

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

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

# Deconstruction

## Queries

## Views

View of the left end of a sequence.

View of the right end of a sequence.

## Indexing

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

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

update :: Int -> a -> Seq a -> Seq aSource

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

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

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