Copyright | (c) Justin Le 2018 |
---|---|
License | BSD3 |
Maintainer | justin@jle.im |
Stability | experimental |
Portability | non-portable |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
Non-Empty Finite Sequences
| An
is a non-empty (but finite) sequence of values of type
NESeq
aa
. Generally has the same interface as NonEmpty
.
This is a non-empty version of Seq
from Data.Sequence.
The main differences between this type and NonEmpty
are:
- You cannot have infinite
NESeq
s - You have constant-time consing from either end, and constant-time
unconsing as well (through
<|
,|>
,:<||
, and:||>
) - Concatenation (
><
,|><
,><|
) is logarithmic-time. - You have logarithmic-time indexing and updating at a given index.
While asymptotics are often better than for NonEmpty
, there is
a decent constant factor involved in most operations.
See documentation for NESeq
for information on how to convert and
manipulate such non-empty sequences
This module essentially re-imports the API of Data.Sequence.Lazy and its
Seq
type, along with semantics and asymptotics.
Because NESeq
is implemented using Seq
, all of the caveats of using
Seq
apply.
All functions take non-empty sequences as inputs. In situations where
their results can be guarunteed to also be non-empty, they also return
non-empty maps. In situations where their results could potentially be
empty, Seq
is returned instead.
Some functions (like spanl
, spanr
, breakl
, breakr
, partition
,
splitAt
) have modified return types to account for possible
configurations of non-emptiness.
Some functions (head
, last
, tail
, init
) are provided because
they are total for non-empty sequences.
This module is intended to be imported qualified, to avoid name clashes with Prelude and Data.Sequence functions:
import qualified Data.Sequence.NonEmpty as NESeq
Synopsis
- data NESeq a where
- pattern IsNonEmpty :: NESeq a -> Seq a
- pattern IsEmpty :: Seq a
- nonEmptySeq :: Seq a -> Maybe (NESeq a)
- toSeq :: NESeq a -> Seq a
- withNonEmpty :: r -> (NESeq a -> r) -> Seq a -> r
- unsafeFromSeq :: Seq a -> NESeq a
- insertSeqAt :: Int -> a -> Seq a -> NESeq a
- singleton :: a -> NESeq a
- (<|) :: a -> NESeq a -> NESeq a
- (|>) :: NESeq a -> a -> NESeq a
- (><) :: NESeq a -> NESeq a -> NESeq a
- (|><) :: NESeq a -> Seq a -> NESeq a
- (><|) :: Seq a -> NESeq a -> NESeq a
- fromList :: NonEmpty a -> NESeq a
- fromFunction :: Int -> (Int -> a) -> NESeq a
- replicate :: Int -> a -> NESeq a
- replicateA :: Applicative f => Int -> f a -> f (NESeq a)
- replicateA1 :: Apply f => Int -> f a -> f (NESeq a)
- replicateM :: Applicative m => Int -> m a -> m (NESeq a)
- cycleTaking :: Int -> NESeq a -> NESeq a
- iterateN :: Int -> (a -> a) -> a -> NESeq a
- unfoldr :: (b -> (a, Maybe b)) -> b -> NESeq a
- unfoldl :: (b -> (Maybe b, a)) -> b -> NESeq a
- head :: NESeq a -> a
- tail :: NESeq a -> Seq a
- last :: NESeq a -> a
- init :: NESeq a -> Seq a
- length :: NESeq a -> Int
- scanl :: (a -> b -> a) -> a -> NESeq b -> NESeq a
- scanl1 :: (a -> a -> a) -> NESeq a -> NESeq a
- scanr :: (a -> b -> b) -> b -> NESeq a -> NESeq b
- scanr1 :: (a -> a -> a) -> NESeq a -> NESeq a
- tails :: NESeq a -> NESeq (NESeq a)
- inits :: NESeq a -> NESeq (NESeq a)
- chunksOf :: Int -> NESeq a -> NESeq (NESeq a)
- takeWhileL :: (a -> Bool) -> NESeq a -> Seq a
- takeWhileR :: (a -> Bool) -> NESeq a -> Seq a
- dropWhileL :: (a -> Bool) -> NESeq a -> Seq a
- dropWhileR :: (a -> Bool) -> NESeq a -> Seq a
- spanl :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
- spanr :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
- breakl :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
- breakr :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
- partition :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
- filter :: (a -> Bool) -> NESeq a -> Seq a
- sort :: Ord a => NESeq a -> NESeq a
- sortBy :: (a -> a -> Ordering) -> NESeq a -> NESeq a
- sortOn :: Ord b => (a -> b) -> NESeq a -> NESeq a
- unstableSort :: Ord a => NESeq a -> NESeq a
- unstableSortBy :: (a -> a -> Ordering) -> NESeq a -> NESeq a
- unstableSortOn :: Ord b => (a -> b) -> NESeq a -> NESeq a
- lookup :: Int -> NESeq a -> Maybe a
- (!?) :: NESeq a -> Int -> Maybe a
- index :: NESeq a -> Int -> a
- adjust :: (a -> a) -> Int -> NESeq a -> NESeq a
- adjust' :: (a -> a) -> Int -> NESeq a -> NESeq a
- update :: Int -> a -> NESeq a -> NESeq a
- take :: Int -> NESeq a -> Seq a
- drop :: Int -> NESeq a -> Seq a
- insertAt :: Int -> a -> NESeq a -> NESeq a
- deleteAt :: Int -> NESeq a -> Seq a
- splitAt :: Int -> NESeq a -> These (NESeq a) (NESeq a)
- elemIndexL :: Eq a => a -> NESeq a -> Maybe Int
- elemIndicesL :: Eq a => a -> NESeq a -> [Int]
- elemIndexR :: Eq a => a -> NESeq a -> Maybe Int
- elemIndicesR :: Eq a => a -> NESeq a -> [Int]
- findIndexL :: (a -> Bool) -> NESeq a -> Maybe Int
- findIndicesL :: (a -> Bool) -> NESeq a -> [Int]
- findIndexR :: (a -> Bool) -> NESeq a -> Maybe Int
- findIndicesR :: (a -> Bool) -> NESeq a -> [Int]
- foldMapWithIndex :: Semigroup m => (Int -> a -> m) -> NESeq a -> m
- foldlWithIndex :: (b -> Int -> a -> b) -> b -> NESeq a -> b
- foldrWithIndex :: (Int -> a -> b -> b) -> b -> NESeq a -> b
- mapWithIndex :: (Int -> a -> b) -> NESeq a -> NESeq b
- traverseWithIndex :: Applicative f => (Int -> a -> f b) -> NESeq a -> f (NESeq b)
- traverseWithIndex1 :: Apply f => (Int -> a -> f b) -> NESeq a -> f (NESeq b)
- reverse :: NESeq a -> NESeq a
- intersperse :: a -> NESeq a -> NESeq a
- zip :: NESeq a -> NESeq b -> NESeq (a, b)
- zipWith :: (a -> b -> c) -> NESeq a -> NESeq b -> NESeq c
- zip3 :: NESeq a -> NESeq b -> NESeq c -> NESeq (a, b, c)
- zipWith3 :: (a -> b -> c -> d) -> NESeq a -> NESeq b -> NESeq c -> NESeq d
- zip4 :: NESeq a -> NESeq b -> NESeq c -> NESeq d -> NESeq (a, b, c, d)
- zipWith4 :: (a -> b -> c -> d -> e) -> NESeq a -> NESeq b -> NESeq c -> NESeq d -> NESeq e
- unzip :: NESeq (a, b) -> (NESeq a, NESeq b)
- unzipWith :: (a -> (b, c)) -> NESeq a -> (NESeq b, NESeq c)
Finite sequences
data NESeq a where infixr 5 Source #
A general-purpose non-empty (by construction) finite sequence type.
Non-emptiness means that:
- Functions that take an
NESeq
can safely operate on it with the assumption that it has at least value. - Functions that return an
NESeq
provide an assurance that the result has at least one value.
Data.Sequence.NonEmpty re-exports the API of Data.Sequence,
faithfully reproducing asymptotics, typeclass constraints, and
semantics. Functions that ensure that input and output maps are both
non-empty (like <|
) return NESeq
, but
functions that might potentially return an empty map (like
tail
) return a Seq
instead.
You can directly construct an NESeq
with the API from
Data.Sequence.NonEmpty; it's more or less the same as constructing
a normal Seq
, except you don't have access to empty
. There
are also a few ways to construct an NESeq
from a Seq
:
- The
nonEmptySeq
smart constructor will convert a
into aSeq
a
, returningMaybe
(NESeq
a)Nothing
if the originalSeq
was empty. - You can use
:<||
,:||>
, andinsertSeqAt
to insert a value into aSeq
to create a guaranteedNESeq
. - You can use the
IsNonEmpty
andIsEmpty
patterns to "pattern match" on aSeq
to reveal it as either containing aNESeq
or an empty sequence. withNonEmpty
offers a continuation-based interface for deconstructing aSeq
and treating it as if it were anNESeq
.
You can convert an NESeq
into a Seq
with toSeq
or
IsNonEmpty
, essentially "obscuring" the
non-empty property from the type.
pattern (:<||) :: a -> Seq a -> NESeq a infixr 5 | O(1). An abstract constructor for an Can be used to match on the head and tail of an |
pattern (:||>) :: Seq a -> a -> NESeq a infixl 5 | O(1). An abstract constructor for an Can be used to match on the init and last of an |
Instances
MonadFix NESeq Source # | |
Defined in Data.Sequence.NonEmpty.Internal | |
MonadZip NESeq Source # | mzipWith = zipWith munzip = unzip |
Foldable NESeq Source # |
|
Defined in Data.Sequence.NonEmpty.Internal fold :: Monoid m => NESeq m -> m # foldMap :: Monoid m => (a -> m) -> NESeq a -> m # foldMap' :: Monoid m => (a -> m) -> NESeq a -> m # foldr :: (a -> b -> b) -> b -> NESeq a -> b # foldr' :: (a -> b -> b) -> b -> NESeq a -> b # foldl :: (b -> a -> b) -> b -> NESeq a -> b # foldl' :: (b -> a -> b) -> b -> NESeq a -> b # foldr1 :: (a -> a -> a) -> NESeq a -> a # foldl1 :: (a -> a -> a) -> NESeq a -> a # elem :: Eq a => a -> NESeq a -> Bool # maximum :: Ord a => NESeq a -> a # minimum :: Ord a => NESeq a -> a # | |
Eq1 NESeq Source # | |
Ord1 NESeq Source # | |
Defined in Data.Sequence.NonEmpty.Internal | |
Read1 NESeq Source # | |
Defined in Data.Sequence.NonEmpty.Internal | |
Show1 NESeq Source # | |
Traversable NESeq Source # | |
Applicative NESeq Source # | |
Functor NESeq Source # | |
Monad NESeq Source # | |
Comonad NESeq Source # | |
Foldable1 NESeq Source # | |
Defined in Data.Sequence.NonEmpty.Internal fold1 :: Semigroup m => NESeq m -> m # foldMap1 :: Semigroup m => (a -> m) -> NESeq a -> m # foldMap1' :: Semigroup m => (a -> m) -> NESeq a -> m # toNonEmpty :: NESeq a -> NonEmpty a # maximum :: Ord a => NESeq a -> a # minimum :: Ord a => NESeq a -> a # foldrMap1 :: (a -> b) -> (a -> b -> b) -> NESeq a -> b # foldlMap1' :: (a -> b) -> (b -> a -> b) -> NESeq a -> b # foldlMap1 :: (a -> b) -> (b -> a -> b) -> NESeq a -> b # foldrMap1' :: (a -> b) -> (a -> b -> b) -> NESeq a -> b # | |
Invariant NESeq Source # | Since: 0.3.4.4 |
Defined in Data.Sequence.NonEmpty.Internal | |
Alt NESeq Source # | |
Apply NESeq Source # | |
Bind NESeq Source # | |
Extend NESeq Source # | |
Traversable1 NESeq Source # | |
FromJSON a => FromJSON (NESeq a) Source # | |
Defined in Data.Sequence.NonEmpty.Internal | |
ToJSON a => ToJSON (NESeq a) Source # | |
Data a => Data (NESeq a) Source # | |
Defined in Data.Sequence.NonEmpty.Internal gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> NESeq a -> c (NESeq a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (NESeq a) # toConstr :: NESeq a -> Constr # dataTypeOf :: NESeq a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (NESeq a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (NESeq a)) # gmapT :: (forall b. Data b => b -> b) -> NESeq a -> NESeq a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> NESeq a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> NESeq a -> r # gmapQ :: (forall d. Data d => d -> u) -> NESeq a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> NESeq a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> NESeq a -> m (NESeq a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> NESeq a -> m (NESeq a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> NESeq a -> m (NESeq a) # | |
Semigroup (NESeq a) Source # | |
Read a => Read (NESeq a) Source # | |
Show a => Show (NESeq a) Source # | |
NFData a => NFData (NESeq a) Source # | |
Defined in Data.Sequence.NonEmpty.Internal | |
Eq a => Eq (NESeq a) Source # | |
Ord a => Ord (NESeq a) Source # | |
Defined in Data.Sequence.NonEmpty.Internal |
Conversions between empty and non-empty sequences
pattern IsNonEmpty :: NESeq a -> Seq a Source #
O(1). The IsNonEmpty
and IsEmpty
patterns allow you to treat
a Seq
as if it were either a
(where IsNonEmpty
nn
is a NESeq
)
or an IsEmpty
.
For example, you can pattern match on a Seq
:
safeHead ::Seq
Int -> Int safeHead (IsNonEmpty
(x :<|| _)) = x -- here, user provided a non-empty sequence, andn
is theNESeq
safeHeadIsEmpty
= 0 -- here the user provided an empty sequence
Matching on
means that the original IsNonEmpty
nSeq
was not
empty, and you have a verified-non-empty NESeq
n
to use.
A case statement handling both IsNonEmpty
and IsEmpty
provides
complete coverage.
This is a bidirectional pattern, so you can use IsNonEmpty
to convert
a NESeq
back into a Seq
, obscuring its non-emptiness (see toSeq
).
pattern IsEmpty :: Seq a Source #
O(1). The IsNonEmpty
and IsEmpty
patterns allow you to treat
a Seq
as if it were either a
(where IsNonEmpty
nn
is
a NESeq
) or an IsEmpty
.
Matching on IsEmpty
means that the original Seq
was empty.
A case statement handling both IsNonEmpty
and IsEmpty
provides
complete coverage.
This is a bidirectional pattern, so you can use IsEmpty
as an
expression, and it will be interpreted as empty
.
See IsNonEmpty
for more information.
nonEmptySeq :: Seq a -> Maybe (NESeq a) Source #
O(1). Smart constructor for an NESeq
from a Seq
. Returns
Nothing
if the Seq
was originally actually empty, and
with an Just
nNESeq
, if the Seq
was not empty.
nonEmptySeq
and
form an
isomorphism: they are perfect structure-preserving inverses of
eachother.maybe
empty
toSeq
See IsNonEmpty
for a pattern synonym that lets
you "match on" the possiblity of a Seq
being an NESeq
.
nonEmptySeq (Data.Sequence.fromList [1,2,3]) == Just (fromList (1) :| [2,3])
toSeq :: NESeq a -> Seq a Source #
O(1).
Convert a non-empty sequence back into a normal possibly-empty sequence,
for usage with functions that expect Seq
.
Can be thought of as "obscuring" the non-emptiness of the map in its
type. See the IsNotEmpty
pattern.
nonEmptySeq
and
form an isomorphism: they are perfect structure-preserving
inverses of eachother.maybe
empty
toSeq
withNonEmpty :: r -> (NESeq a -> r) -> Seq a -> r Source #
O(log n). A general continuation-based way to consume a Seq
as if
it were an NESeq
.
will take a withNonEmpty
def fSeq
. If map is
empty, it will evaluate to def
. Otherwise, a non-empty map NESeq
will be fed to the function f
instead.
nonEmptySeq
==withNonEmpty
Nothing
Just
unsafeFromSeq :: Seq a -> NESeq a Source #
O(1). Unsafe version of nonEmptySeq
. Coerces a Seq
into an
NESeq
, but is undefined (throws a runtime exception when evaluation is
attempted) for an empty Seq
.
Construction
(<|) :: a -> NESeq a -> NESeq a infixr 5 Source #
\( O(1) \). Add an element to the left end of a non-empty sequence. Mnemonic: a triangle with the single element at the pointy end.
(|>) :: NESeq a -> a -> NESeq a infixl 5 Source #
\( O(1) \). Add an element to the right end of a non-empty sequence. Mnemonic: a triangle with the single element at the pointy end.
(><) :: NESeq a -> NESeq a -> NESeq a infixr 5 Source #
\( O(\log(\min(n_1,n_2))) \). Concatenate two non-empty sequences.
fromList :: NonEmpty a -> NESeq a Source #
\( O(n) \). Create a sequence from a finite list of elements. There
is a function toNonEmpty
in the opposite direction for all instances
of the Foldable1
class, including NESeq
.
fromFunction :: Int -> (Int -> a) -> NESeq a Source #
\( O(n) \). Convert a given sequence length and a function representing that sequence into a sequence.
Repetition
replicate :: Int -> a -> NESeq a Source #
\( O(\log n) \). replicate n x
is a sequence consisting of n
copies of x
. Is only defined when n
is positive.
replicateA :: Applicative f => Int -> f a -> f (NESeq a) Source #
replicateA
is an Applicative
version of replicate
, and makes (
O(log n) ) calls to liftA2
and pure
. Is only defined when n
is
positive.
replicateA n x = sequenceA (replicate n x)
Is a more restrictive version of replicateA1
. replicateA1
should be
preferred whenever possible.
replicateA1 :: Apply f => Int -> f a -> f (NESeq a) Source #
replicateA
is an Apply
version of replicate
, and makes ( O(log
n) ) calls to <.>
. Is only defined when n
is positive.
replicateA1 n x = sequence1 (replicate n x)
replicateM :: Applicative m => Int -> m a -> m (NESeq a) Source #
An alias of replicateA
.
cycleTaking :: Int -> NESeq a -> NESeq a Source #
O(log k).
forms a sequence of length cycleTaking
k xsk
by
repeatedly concatenating xs
with itself. Is only defined when k
is
positive.
cycleTaking k = fromList . fromJust . nonEmpty . take k . cycle . toList
Iterative construction
iterateN :: Int -> (a -> a) -> a -> NESeq a Source #
\( O(n) \). Constructs a sequence by repeated application of a function to a seed value. Is only defined if given a positive value.
iterateN n f x = fromList (fromJust (nonEmpty ((Prelude.take n (Prelude.iterate f x)))))
unfoldr :: (b -> (a, Maybe b)) -> b -> NESeq a Source #
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.
Deconstruction
O(1). Retrieve the left-most item in a non-empty sequence. Note that this function is total.
O(1). Retrieve the right-most item in a non-empty sequence. Note that this function is total.
Queries
Scans
Sublists
tails :: NESeq a -> NESeq (NESeq a) Source #
\( O(n) \). Returns a sequence of all non-empty suffixes of this sequence, longest first. For example,
tails (fromList (1:|[2,3])) = fromList (fromList (1:|[2,3]) :| [fromList (2:|[3]), fromList (3:|[])])
Evaluating the \( i \)th suffix takes \( O(\log(\min(i, n-i))) \), but evaluating every suffix in the sequence takes \( O(n) \) due to sharing.
inits :: NESeq a -> NESeq (NESeq a) Source #
\( O(n) \). Returns a sequence of all non-empty prefixes of this sequence, shortest first. For example,
tails (fromList (1:|[2,3])) = fromList (fromList (1:|[]) :| [fromList (1:|[2]), fromList (1:|[2,3]))
Evaluating the \( i \)th prefix takes \( O(\log(\min(i, n-i))) \), but evaluating every prefix in the sequence takes \( O(n) \) due to sharing.
chunksOf :: Int -> NESeq a -> NESeq (NESeq a) Source #
\(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. Is only defined if c
is a positive
number.
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) \)
Sequential searches
takeWhileL :: (a -> Bool) -> NESeq a -> Seq a Source #
\( 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
.
Returns a possibly empty sequence (Seq
) in the case that the predicate
fails on the first item.
takeWhileR :: (a -> Bool) -> NESeq a -> Seq a Source #
\( 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
.
Returns a possibly empty sequence (Seq
) in the case that the predicate
fails on the first item.
is equivalent to takeWhileR
p xs
.reverse
(takeWhileL
p (reverse
xs))
dropWhileL :: (a -> Bool) -> NESeq a -> Seq a Source #
\( O(i) \) where \( i \) is the prefix length.
returns
the suffix remaining after dropWhileL
p xs
.takeWhileL
p xs
Returns a possibly empty sequence (Seq
) in the case that the predicate
passes for all items.
dropWhileR :: (a -> Bool) -> NESeq a -> Seq a Source #
\( O(i) \) where \( i \) is the suffix length.
returns
the prefix remaining after dropWhileR
p xs
.takeWhileR
p xs
Returns a possibly empty sequence (Seq
) in the case that the predicate
passes for all items.
is equivalent to dropWhileR
p xs
.reverse
(dropWhileL
p (reverse
xs))
spanl :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a) Source #
\( O(i) \) where \( i \) is the prefix length. spanl
, applied to
a predicate p
and a sequence xs
, returns a These
based on the
point where the predicate fails:
means that the predicate was true for all items, andThis
ysys
is the entire original sequence.
means that the predicate failed on the first item, andThat
zszs
is the entire original sequence.
givesThese
ys zsys
(the prefix of elements that satisfy the predicae) andzs
(the remainder of the sequence)
spanr :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a) Source #
\( O(i) \) where \( i \) is the suffix length. spanr
, applied to
a predicate p
and a sequence xs
, returns a These
based on the
point where the predicate fails:
means that the predicate was true for all items, andThis
ysys
is the entire original sequence.
means that the predicate failed on the first item, andThat
zszs
is the entire original sequence.
givesThese
ys zsys
(the suffix of elements that satisfy the predicae) andzs
(the remainder of the sequence, before the suffix)
partition :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a) Source #
\( O(n) \). The partition
function takes a predicate p
and a
sequence xs
and returns sequences of those elements which do and
do not satisfy the predicate, as a These
:
means that the predicate was true for all items, andThis
ysys
is the entire original sequence.
means that the predicate failed on the first item, andThat
zszs
is the entire original sequence.
givesThese
ys zsys
(the sequence of elements for which the predicate was true) andzs
(the sequence of elements for which the predicate was false).
Sorting
sort :: Ord a => NESeq a -> NESeq a Source #
\( O(n \log n) \). sort
sorts the specified NESeq
by the natural
ordering of its elements. The sort is stable. If stability is not
required, unstableSort
can be slightly faster.
sortBy :: (a -> a -> Ordering) -> NESeq a -> NESeq a Source #
\( O(n \log n) \). sortBy
sorts the specified NESeq
according to
the specified comparator. The sort is stable. If stability is not
required, unstableSortBy
can be slightly faster.
sortOn :: Ord b => (a -> b) -> NESeq a -> NESeq a Source #
\( O(n \log n) \). sortOn
sorts the specified NESeq
by comparing
the results of a key function applied to each element.
is
equivalent to sortOn
f
, but has the
performance advantage of only evaluating sortBy
(compare
`on`
f)f
once for each element in
the input list. This is called the decorate-sort-undecorate paradigm, or
Schwartzian transform.
An example of using sortOn
might be to sort a NESeq
of strings
according to their length:
sortOn length (fromList ("alligator" :| ["monkey", "zebra"])) == fromList ("zebra" :| ["monkey", "alligator"])
If, instead, sortBy
had been used, length
would be evaluated on
every comparison, giving \( O(n \log n) \) evaluations, rather than
\( O(n) \).
If f
is very cheap (for example a record selector, or fst
),
will be faster than
sortBy
(compare
`on`
f)
.sortOn
f
unstableSort :: Ord a => NESeq a -> NESeq a Source #
\( O(n \log n) \). unstableSort
sorts the specified NESeq
by the
natural ordering of its elements, but the sort is not stable. This
algorithm is frequently faster and uses less memory than sort
.
unstableSortBy :: (a -> a -> Ordering) -> NESeq a -> NESeq a Source #
\( O(n \log n) \). A generalization of unstableSort
,
unstableSortBy
takes an arbitrary comparator and sorts the specified
sequence. The sort is not stable. This algorithm is frequently faster
and uses less memory than sortBy
.
unstableSortOn :: Ord b => (a -> b) -> NESeq a -> NESeq a Source #
\( O(n \log n) \). unstableSortOn
sorts the specified NESeq
by
comparing the results of a key function applied to each element.
is equivalent to unstableSortOn
f
,
but has the performance advantage of only evaluating unstableSortBy
(compare
`on`
f)f
once for each
element in the input list. This is called the
decorate-sort-undecorate paradigm, or Schwartzian transform.
An example of using unstableSortOn
might be to sort a NESeq
of strings
according to their length.
unstableSortOn length (fromList ("alligator" :| ["monkey", "zebra"])) == fromList ("zebra" :| ["monkey", "alligator]")
If, instead, unstableSortBy
had been used, length
would be evaluated on
every comparison, giving \( O(n \log n) \) evaluations, rather than
\( O(n) \).
If f
is very cheap (for example a record selector, or fst
),
will be faster than
unstableSortBy
(compare
`on`
f)
.unstableSortOn
f
Indexing
(!?) :: NESeq a -> Int -> Maybe a Source #
\( O(\log(\min(i,n-i))) \). A flipped, infix version of lookup
.
index :: NESeq a -> Int -> a Source #
\( 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.
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 (!?)
.
adjust :: (a -> a) -> Int -> NESeq a -> NESeq a Source #
\( 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.
adjust' :: (a -> a) -> Int -> NESeq a -> NESeq a Source #
\( 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
update :: Int -> a -> NESeq a -> NESeq a Source #
\( O(\log(\min(i,n-i))) \). Replace the element at the specified position. If the position is out of range, the original sequence is returned.
take :: Int -> NESeq a -> Seq 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 si
elements, the whole sequence
is returned.
drop :: Int -> NESeq a -> Seq 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 si
elements, the empty sequence
is returned.
insertAt :: Int -> a -> NESeq a -> NESeq a Source #
\( O(\log(\min(i,n-i))) \).
inserts insertAt
i x xsx
into xs
at the index i
, shifting the rest of the sequence over.
insertAt 2 x (fromList (a:|[b,c,d])) = fromList (a:|[b,x,c,d]) insertAt 4 x (fromList (a:|[b,c,d])) = insertAt 10 x (fromList (a:|[b,c,d])) = fromList (a:|[b,c,d,x])
insertAt i x xs = take i xs >< singleton x >< drop i xs
deleteAt :: Int -> NESeq a -> Seq a Source #
\( O(\log(\min(i,n-i))) \). Delete the element of a sequence at a given index. Return the original sequence if the index is out of range.
deleteAt 2 (a:|[b,c,d]) = a:|[b,d] deleteAt 4 (a:|[b,c,d]) = deleteAt (-1) (a:|[b,c,d]) = a:|[b,c,d]
splitAt :: Int -> NESeq a -> These (NESeq a) (NESeq a) Source #
\( O(\log(\min(i,n-i))) \). Split a sequence at a given position.
means that the given position was longer than the length of the list, andThis
ysys
is the entire original system.
means that the given position was zero or smaller, and soThat
zszs
is the entire original sequence.
givesThese
ys zsys
(the sequence of elements before the given position,take n xs
) andzs
(the sequence of elements after the given position,drop n xs
).
Indexing with predicates
These functions perform sequential searches from the left or right ends of the sequence returning indices of matching elements.
elemIndexL :: Eq a => a -> NESeq a -> Maybe Int Source #
elemIndexL
finds the leftmost index of the specified element,
if it is present, and otherwise Nothing
.
elemIndicesL :: Eq a => a -> NESeq a -> [Int] Source #
elemIndicesL
finds the indices of the specified element, from
left to right (i.e. in ascending order).
elemIndexR :: Eq a => a -> NESeq a -> Maybe Int Source #
elemIndexR
finds the rightmost index of the specified element,
if it is present, and otherwise Nothing
.
elemIndicesR :: Eq a => a -> NESeq a -> [Int] Source #
elemIndicesR
finds the indices of the specified element, from
right to left (i.e. in descending order).
findIndexL :: (a -> Bool) -> NESeq a -> Maybe Int Source #
finds the index of the leftmost element that
satisfies findIndexL
p xsp
, if any exist.
findIndicesL :: (a -> Bool) -> NESeq a -> [Int] Source #
finds all indices of elements that satisfy findIndicesL
pp
,
in ascending order.
findIndexR :: (a -> Bool) -> NESeq a -> Maybe Int Source #
finds the index of the rightmost element that
satisfies findIndexR
p xsp
, if any exist.
findIndicesR :: (a -> Bool) -> NESeq a -> [Int] Source #
finds all indices of elements that satisfy findIndicesR
pp
,
in descending order.
Folds
foldMapWithIndex :: Semigroup m => (Int -> a -> m) -> NESeq a -> m Source #
O(n). A generalization of foldMap1
, foldMapWithIndex
takes
a folding function that also depends on the element's index, and applies
it to every element in the sequence.
foldlWithIndex :: (b -> Int -> a -> b) -> b -> NESeq a -> b Source #
foldlWithIndex
is a version of foldl
that also provides access
to the index of each element.
foldrWithIndex :: (Int -> a -> b -> b) -> b -> NESeq a -> b Source #
foldrWithIndex
is a version of foldr
that also provides access
to the index of each element.
Transformations
mapWithIndex :: (Int -> a -> b) -> NESeq a -> NESeq b Source #
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.
traverseWithIndex :: Applicative f => (Int -> a -> f b) -> NESeq a -> f (NESeq b) Source #
traverseWithIndex
is a version of traverse
that also offers
access to the index of each element.
Is a more restrictive version of traverseWithIndex1
;
traverseWithIndex1
should be used whenever possible.
traverseWithIndex1 :: Apply f => (Int -> a -> f b) -> NESeq a -> f (NESeq b) Source #
O(n). traverseWithIndex1
is a version of traverse1
that also
offers access to the index of each element.
intersperse :: a -> NESeq a -> NESeq a Source #
\( O(n) \). Intersperse an element between the elements of a sequence.
intersperse a empty = empty intersperse a (singleton x) = singleton x intersperse a (fromList [x,y]) = fromList [x,a,y] intersperse a (fromList [x,y,z]) = fromList [x,a,y,a,z]
Zips and unzip
zip :: NESeq a -> NESeq b -> NESeq (a, b) Source #
\( 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.
unzipWith :: (a -> (b, c)) -> NESeq a -> (NESeq b, NESeq c) Source #
\( O(n) \). Unzip a sequence using a function to divide elements.
unzipWith f xs ==unzip
(fmap
f xs)
Efficiency note:
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.