containers-0.2.0.1: Assorted concrete container types

Data.Sequence

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

data Seq a Source

General-purpose finite sequences.

Instances

 Monad Seq Functor Seq Typeable1 Seq MonadPlus Seq Foldable Seq Traversable Seq Eq a => Eq (Seq a) Data a => Data (Seq a) Ord a => Ord (Seq a) Read a => Read (Seq a) Show a => Show (Seq a) Monoid (Seq a)

# Construction

O(1). The empty sequence.

singleton :: a -> Seq aSource

O(1). A singleton sequence.

(<|) :: 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.

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

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

fromList :: [a] -> Seq aSource

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

O(1). Is this the empty sequence?

length :: Seq a -> IntSource

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

## Views

data ViewL a Source

View of the left end of a sequence.

Constructors

 EmptyL empty sequence a :< (Seq a) leftmost element and the rest of the sequence

Instances

 Functor ViewL Typeable1 ViewL Foldable ViewL Traversable ViewL Eq a => Eq (ViewL a) Data a => Data (ViewL a) Ord a => Ord (ViewL a) Read a => Read (ViewL a) Show a => Show (ViewL a)

viewl :: Seq a -> ViewL aSource

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

data ViewR a Source

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

 Functor ViewR Typeable1 ViewR Foldable ViewR Traversable ViewR Eq a => Eq (ViewR a) Data a => Data (ViewR a) Ord a => Ord (ViewR a) Read a => Read (ViewR a) Show a => Show (ViewR a)

viewr :: Seq a -> ViewR aSource

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

## Indexing

index :: Seq a -> Int -> aSource

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 aSource

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 aSource

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 aSource

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.

drop :: Int -> Seq a -> Seq aSource

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.

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

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 aSource

O(n). The reverse of a sequence.