| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.Sequence.Strict
Description
Strict variants of
Seq
operations.
Synopsis
- data StrictSeq a where
- fromStrict :: StrictSeq a -> Seq a
- forceToStrict :: Seq a -> StrictSeq a
- empty :: StrictSeq a
- singleton :: a -> StrictSeq a
- (<|) :: a -> StrictSeq a -> StrictSeq a
- (|>) :: StrictSeq a -> a -> StrictSeq a
- (><) :: StrictSeq a -> StrictSeq a -> StrictSeq a
- fromList :: [a] -> StrictSeq a
- null :: StrictSeq a -> Bool
- length :: StrictSeq a -> Int
- scanl :: (a -> b -> a) -> a -> StrictSeq b -> StrictSeq a
- dropWhileL :: (a -> Bool ) -> StrictSeq a -> StrictSeq a
- dropWhileR :: (a -> Bool ) -> StrictSeq a -> StrictSeq a
- spanl :: (a -> Bool ) -> StrictSeq a -> ( StrictSeq a, StrictSeq a)
- spanr :: (a -> Bool ) -> StrictSeq a -> ( StrictSeq a, StrictSeq a)
- lookup :: Int -> StrictSeq a -> Maybe a
- (!?) :: StrictSeq a -> Int -> Maybe a
- take :: Int -> StrictSeq a -> StrictSeq a
- takeLast :: Int -> StrictSeq a -> StrictSeq a
- drop :: Int -> StrictSeq a -> StrictSeq a
- dropLast :: Int -> StrictSeq a -> StrictSeq a
- splitAt :: Int -> StrictSeq a -> ( StrictSeq a, StrictSeq a)
- splitAtEnd :: Int -> StrictSeq a -> ( StrictSeq a, StrictSeq a)
- findIndexL :: (a -> Bool ) -> StrictSeq a -> Maybe Int
- findIndicesL :: (a -> Bool ) -> StrictSeq a -> [ Int ]
- findIndexR :: (a -> Bool ) -> StrictSeq a -> Maybe Int
- findIndicesR :: (a -> Bool ) -> StrictSeq a -> [ Int ]
- zip :: StrictSeq a -> StrictSeq b -> StrictSeq (a, b)
- zipWith :: (a -> b -> c) -> StrictSeq a -> StrictSeq b -> StrictSeq c
- unzip :: StrictSeq (a, b) -> ( StrictSeq a, StrictSeq b)
- unzipWith :: (a -> (b, c)) -> StrictSeq a -> ( StrictSeq b, StrictSeq c)
Documentation
data StrictSeq a where Source #
A
newtype
wrapper around a
Seq
, representing a general-purpose finite
sequence that is strict in its values.
This strictness is not enforced at the type level, but rather by the construction functions in this module. These functions essentially just wrap the original Data.Sequence functions while forcing the provided value to WHNF.
Bundled Patterns
| pattern Empty :: StrictSeq a |
A bidirectional pattern synonym matching an empty sequence. |
| pattern (:<|) :: a -> StrictSeq a -> StrictSeq a infixr 5 |
A bidirectional pattern synonym viewing the front of a non-empty sequence. |
| pattern (:|>) :: StrictSeq a -> a -> StrictSeq a infixl 5 |
A bidirectional pattern synonym viewing the rear of a non-empty sequence. |
Instances
fromStrict :: StrictSeq a -> Seq a Source #
forceToStrict :: Seq a -> StrictSeq a Source #
Construction
(<|) :: a -> StrictSeq a -> StrictSeq a infixr 5 Source #
\( O(1) \) . Add an element to the left end of a sequence. Mnemonic: a triangle with the single element at the pointy end.
(|>) :: StrictSeq a -> a -> StrictSeq a infixl 5 Source #
\( O(1) \) . Add an element to the right end of a sequence. Mnemonic: a triangle with the single element at the pointy end.
(><) :: StrictSeq a -> StrictSeq a -> StrictSeq a infixr 5 Source #
\( O(\log(\min(n_1,n_2))) \) . Concatenate two sequences.
Deconstruction
Queries
Scans
Sublists
Sequential searches
dropWhileL :: (a -> Bool ) -> StrictSeq a -> StrictSeq a Source #
\( O(i) \)
where
\( i \)
is the prefix length.
returns
the suffix remaining after
dropWhileL
p xs
.
takeWhileL
p xs
dropWhileR :: (a -> Bool ) -> StrictSeq a -> StrictSeq a Source #
\( O(i) \)
where
\( i \)
is the suffix length.
returns
the prefix remaining after
dropWhileR
p xs
.
takeWhileR
p xs
is equivalent to
dropWhileR
p xs
.
reverse
(
dropWhileL
p (
reverse
xs))
spanl :: (a -> Bool ) -> StrictSeq a -> ( StrictSeq a, StrictSeq a) Source #
\( 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.
spanr :: (a -> Bool ) -> StrictSeq a -> ( StrictSeq a, StrictSeq a) Source #
\( 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.
Indexing
lookup :: Int -> StrictSeq a -> Maybe a Source #
\( 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
.
0 <= i < length xs ==> lookup i xs == Just (toList xs !! i)
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
Map
m
at key
k
, you could use
case lookup 5 xs of
Nothing -> m
Just x -> insert k x m
(!?) :: StrictSeq a -> Int -> Maybe a Source #
\( O(\log(\min(i,n-i))) \)
. A flipped, infix version of
lookup
.
take :: Int -> StrictSeq a -> StrictSeq a Source #
\( O(\log(\min(i,n-i))) \)
. The first
i
elements of a sequence.
If
i
is negative,
yields the empty sequence.
If the sequence contains fewer than
take
i s
i
elements, the whole sequence
is returned.
takeLast :: Int -> StrictSeq a -> StrictSeq a Source #
Take the last
n
elements
Returns the entire sequence if it has fewer than
n
elements.
Inherits asymptotic complexity from
drop
.
drop :: Int -> StrictSeq a -> StrictSeq a Source #
\( O(\log(\min(i,n-i))) \)
. Elements of a sequence after the first
i
.
If
i
is negative,
yields the whole sequence.
If the sequence contains fewer than
drop
i s
i
elements, the empty sequence
is returned.
dropLast :: Int -> StrictSeq a -> StrictSeq a Source #
Drop the last
n
elements
Returns the
Empty
sequence if it has fewer than
n
elements.
Inherits asymptotic complexity from
take
.
splitAtEnd :: Int -> StrictSeq a -> ( StrictSeq a, StrictSeq a) Source #
Split at the given position counting from the end of the sequence.
Inherits asymptotic complexity from
splitAt
.
Indexing with predicates
findIndexL :: (a -> Bool ) -> StrictSeq a -> Maybe Int Source #
finds the index of the leftmost element that
satisfies
findIndexL
p xs
p
, if any exist.
findIndicesL :: (a -> Bool ) -> StrictSeq a -> [ Int ] Source #
finds all indices of elements that satisfy
findIndicesL
p
p
, in
ascending order.
findIndexR :: (a -> Bool ) -> StrictSeq a -> Maybe Int Source #
finds the index of the rightmost element that
satisfies
findIndexR
p xs
p
, if any exist.
findIndicesR :: (a -> Bool ) -> StrictSeq a -> [ Int ] Source #
finds all indices of elements that satisfy
findIndicesR
p
p
, in
descending order.