The contents of this module may change in any way whatsoever
and without any warning between minor versions of this package.
Authors importing this module are expected to track development
closely.
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.
Warning: The size of a Seq must not exceed maxBound::Int. Violation
of this condition is not detected and if the size limit is exceeded, the
behaviour of the sequence is undefined. This is unlikely to occur in most
applications, but some care may be required when using ><, <*>, *>, or
>>, particularly repeatedly and particularly in combination with
replicate or fromFunction.
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.
O(n) . Create a sequence consisting of the elements of an Array.
Note that the resulting sequence elements may be evaluated lazily (as on GHC),
so you must force the entire structure to be sure that the original array
can be garbage-collected.
Builds a sequence from a seed value. Takes time linear in the
number of generated elements. WARNING: If the number of generated
elements is infinite, this method will not terminate.
O \Bigl(\bigl(\frac{n}{c}\bigr) \log c\Bigr). chunksOf c xs splits xs into chunks of size c>0.
If c does not divide the length of xs evenly, then the last element
of the result will be short.
Side note: the given performance bound is missing some messy terms that only
really affect edge cases. Performance degrades smoothly from O(1) (for
c = n ) to O(n) (for c = 1 ). The true bound is more like
O \Bigl( \bigl(\frac{n}{c} - 1\bigr) (\log (c + 1)) + 1 \Bigr)
O(i) where i is the prefix length. takeWhileL, applied
to a predicate p and a sequence xs, returns the longest prefix
(possibly empty) of xs of elements that satisfy p.
O(i) where i is the suffix length. takeWhileR, applied
to a predicate p and a sequence xs, returns the longest suffix
(possibly empty) of xs of elements that satisfy p.
O(i) where i is the prefix length. spanl, applied to
a predicate p and a sequence xs, returns a pair whose first
element is the longest prefix (possibly empty) of xs of elements that
satisfy p and the second element is the remainder of the sequence.
O(i) where i is the suffix length. spanr, applied to a
predicate p and a sequence xs, returns a pair whose first element
is the longest suffix (possibly empty) of xs of elements that
satisfy p and the second element is the remainder of the sequence.
O(i) where i is the breakpoint index. breakl, applied to a
predicate p and a sequence xs, returns a pair whose first element
is the longest prefix (possibly empty) of xs of elements that
do not satisfyp and the second element is the remainder of
the sequence.
O(\log(\min(i,n-i))) . The element at the specified position,
counting from 0. If the specified position is negative or at
least the length of the sequence, lookup returns Nothing.
Property
prop> 0 <= i < length xs ==> lookup i xs == Just (toList xs !! i)
Property
prop> i < 0 || i >= length xs ==> lookup i xs = Nothing
Unlike index, this can be used to retrieve an element without
forcing it. For example, to insert the fifth element of a sequence
xs into a Data.Map.Lazy.Mapm at key k, you could use
case lookup 5 xs of
Nothing -> m
Just x -> insert k x m
O(\log(\min(i,n-i))) . The element at the specified position,
counting from 0. The argument should thus be a non-negative
integer less than the size of the sequence.
If the position is out of range, index fails with an error.
Property
prop> xs `index` i = toList xs !! i
Caution: index necessarily delays retrieving the requested
element until the result is forced. It can therefore lead to a space
leak if the result is stored, unforced, in another structure. To retrieve
an element immediately without forcing it, use lookup or (!?).
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. adjust
can lead to poor performance and even memory leaks, because it does not
force the new value before installing it in the sequence. adjust' should
usually be preferred.
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.
The new value is forced before it is installed in the sequence.
adjust' f i xs =
case xs !? i of
Nothing -> xs
Just x -> let !x' = f x
in update i x' xs
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.
O(\log(\min(i,n-i))) . Elements of a sequence after the first i.
If i is negative, drop i s yields the whole sequence.
If the sequence contains fewer than i elements, the empty sequence
is returned.
A generalization of fmap, mapWithIndex takes a mapping
function that also depends on the element's index, and applies it to every
element in the sequence.
O(\min(n_1,n_2)) . zip takes two sequences and returns a sequence
of corresponding pairs. If one input is short, excess elements are
discarded from the right end of the longer sequence.
O(\min(n_1,n_2)) . zipWith generalizes zip by zipping with the
function given as the first argument, instead of a tupling function.
For example, zipWith (+) is applied to two sequences to take the
sequence of corresponding sums.
O(\min(n_1,n_2,n_3)) . zipWith3 takes a function which combines
three elements, as well as three sequences and returns a sequence of
their point-wise combinations, analogous to zipWith.
O(\min(n_1,n_2,n_3,n_4)) . zipWith4 takes a function which combines
four elements, as well as four sequences and returns a sequence of
their point-wise combinations, analogous to zipWith.
unzipWith produces its two results in lockstep. If you calculate
unzipWith f xs and fully force either of the results, then the
entire structure of the other one will be built as well. This
behavior allows the garbage collector to collect each calculated
pair component as soon as it dies, without having to wait for its mate
to die. If you do not need this behavior, you may be better off simply
calculating the sequence of pairs and using fmap to extract each
component sequence.