| containers-0.1.0.2: Assorted concrete container types | Source code | Contents | Index

Data.Sequence

Portability | portable
Stability | experimental
Maintainer | libraries@haskell.org

Contents

Construction
Deconstruction
  Queries
  Views
  Indexing
Transformations

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

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

Synopsis

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

= EmptyL
| (:<) a (Seq a)

viewl :: Seq a -> ViewL a

data ViewR a

= EmptyR
| (:>) (Seq a) 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

data Seq a | Source

General-purpose finite sequences.
Instances

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

Construction

empty :: Seq a | Source

O(1). The empty sequence.

singleton :: a -> Seq a | Source

O(1). A singleton sequence.

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

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

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

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

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

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

O(1). Is this the empty sequence?

length :: Seq a -> Int | Source

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

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

viewl :: Seq a -> ViewL a | Source

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

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

viewr :: Seq a -> ViewR a | Source

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

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

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

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

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

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

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

O(n). The reverse of a sequence.
Produced by Haddock version 0.9