| Haskell Hierarchical Libraries (base package) | Source code | Contents | Index

Data.Sequence

Portability | portable
Stability | experimental
Maintainer | ross@soi.city.ac.uk

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

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

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
O(1). Analyse the left end of a sequence.
data ViewR a

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
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
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 a 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.
Transformations
reverse :: Seq a -> Seq a
O(n). The reverse of a sequence.
Produced by Haddock version 0.8