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





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 23 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 
Generalpurpose finite sequences.
 Instances  


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.


Deconstruction


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  


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  


viewr :: Seq a > ViewR a 
O(1). Analyse the right end of a sequence.


Indexing


index :: Seq a > Int > a 
O(log(min(i,ni))). The element at the specified position


adjust :: (a > a) > Int > Seq a > Seq a 
O(log(min(i,ni))). Update the element at the specified position


update :: Int > a > Seq a > Seq a 
O(log(min(i,ni))). Replace the element at the specified position


take :: Int > Seq a > Seq a 
O(log(min(i,ni))). The first i elements of a sequence.


drop :: Int > Seq a > Seq a 
O(log(min(i,ni))). Elements of a sequence after the first i.


splitAt :: Int > Seq a > (Seq a, Seq a) 
O(log(min(i,ni))). 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 