Gtk2HsContentsIndex
Graphics.UI.Gtk.ModelView.Sequence
Portabilityportable
Stabilityexperimental
Maintainerross@soi.city.ac.uk
Contents
Construction
Deconstruction
Views
Indexing
Lists
Folds
Right associative
Left associative
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

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
null :: Seq a -> Bool
data ViewL a
= EmptyL
| (:<) a (Seq a)
viewl :: Seq a -> ViewL a
data ViewR a
= EmptyR
| (:>) (Seq a) a
viewr :: Seq a -> ViewR a
length :: Seq a -> Int
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)
fromList :: [a] -> Seq a
toList :: Seq a -> [a]
foldr :: (a -> b -> b) -> b -> Seq a -> b
foldr1 :: (a -> a -> a) -> Seq a -> a
foldr' :: (a -> b -> b) -> b -> Seq a -> b
foldrM :: Monad m => (a -> b -> m b) -> b -> Seq a -> m b
foldl :: (a -> b -> a) -> a -> Seq b -> a
foldl1 :: (a -> a -> a) -> Seq a -> a
foldl' :: (a -> b -> a) -> a -> Seq b -> a
foldlM :: Monad m => (a -> b -> m a) -> a -> Seq b -> m a
reverse :: Seq a -> Seq a
Documentation
data Seq a
General-purpose finite sequences.
show/hide Instances
Functor Seq
Eq a => Eq (Seq a)
Ord a => Ord (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.
Deconstruction
null :: Seq a -> Bool
O(1). Is this the empty sequence?
Views
data ViewL a
View of the left end of a sequence.
Constructors
EmptyLempty sequence
(:<) a (Seq a)leftmost element and the rest of the sequence
show/hide Instances
Functor ViewL
(Eq a, ??? a) => Eq (ViewL a)
(Show a, ??? 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
EmptyRempty sequence
(:>) (Seq a) athe sequence minus the rightmost element, and the rightmost element
show/hide Instances
Functor ViewR
(Eq a, ??? a) => Eq (ViewR a)
(Show a, ??? a) => Show (ViewR a)
viewr :: Seq a -> ViewR a
O(1). Analyse the right end of a sequence.
Indexing
length :: Seq a -> Int
O(1). The number of elements in the sequence.
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 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.
Lists
fromList :: [a] -> Seq a
O(n). Create a sequence from a finite list of elements.
toList :: Seq a -> [a]
O(n). List of elements of the sequence.
Folds
Right associative
foldr :: (a -> b -> b) -> b -> Seq a -> b
O(n*t). Fold over the elements of a sequence, associating to the right.
foldr1 :: (a -> a -> a) -> Seq a -> a
O(n*t). A variant of foldr that has no base case, and thus may only be applied to non-empty sequences.
foldr' :: (a -> b -> b) -> b -> Seq a -> b
O(n*t). Fold over the elements of a sequence, associating to the right, but strictly.
foldrM :: Monad m => (a -> b -> m b) -> b -> Seq a -> m b
O(n*t). Monadic fold over the elements of a sequence, associating to the right, i.e. from right to left.
Left associative
foldl :: (a -> b -> a) -> a -> Seq b -> a
O(n*t). Fold over the elements of a sequence, associating to the left.
foldl1 :: (a -> a -> a) -> Seq a -> a
O(n*t). A variant of foldl that has no base case, and thus may only be applied to non-empty sequences.
foldl' :: (a -> b -> a) -> a -> Seq b -> a
O(n*t). Fold over the elements of a sequence, associating to the right, but strictly.
foldlM :: Monad m => (a -> b -> m a) -> a -> Seq b -> m a
O(n*t). Monadic fold over the elements of a sequence, associating to the left, i.e. from left to right.
Transformations
reverse :: Seq a -> Seq a
O(n). The reverse of a sequence.
Produced by Haddock version 0.8