nonempty-containers-0.3.5.0: Non-empty variants of containers data types, with full API

Copyright | (c) Justin Le 2018
License | BSD3
Maintainer | justin@jle.im
Stability | experimental
Portability | non-portable
Safe Haskell | None
Language | Haskell2010

Data.Sequence.NonEmpty

Contents

- Finite sequences
  - Conversions between empty and non-empty sequences
- Construction
  - Repetition
  - Iterative construction
- Deconstruction
  - Queries
- Scans
- Sublists
  - Sequential searches
- Sorting
- Indexing
  - Indexing with predicates
- Folds
- Transformations
  - Zips and unzip

Description

# Non-Empty Finite Sequences

| An ``NESeq` a` is a non-empty (but finite) sequence of values of type `a`. 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 (:<||) :: a -> Seq a -> NESeq a
  - pattern (:||>) :: Seq a -> a -> NESeq a
- 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`:

1. The `nonEmptySeq` smart constructor will convert a ``Seq` a` into a ``Maybe` (`NESeq` a)`, returning `Nothing` if the original `Seq` was empty.
2. You can use `:<||`, `:||>`, and `insertSeqAt` to insert a value into a `Seq` to create a guaranteed `NESeq`.
3. You can use the `IsNonEmpty` and `IsEmpty` patterns to "pattern match" on a `Seq` to reveal it as either containing a `NESeq` or an empty sequence.
4. `withNonEmpty` offers a continuation-based interface for deconstructing a `Seq` and treating it as if it were an `NESeq`.

You can convert an `NESeq` into a `Seq` with `toSeq` or `IsNonEmpty`, essentially "obscuring" the non-empty property from the type.

Bundled Patterns

pattern (:<||) :: a -> Seq a -> NESeq a infixr 5 | O(1). An abstract constructor for an `NESeq` that consists of a "head" `a` and a "tail" ``Seq` a`. Similar to `:|` for `NonEmpty`. Can be used to match on the head and tail of an `NESeq`, and also used to construct an `NESeq` by consing an item to the beginnong of a `Seq`, ensuring that the result is non-empty.

pattern (:||>) :: Seq a -> a -> NESeq a infixl 5

O(1). An abstract constructor for an `NESeq` that consists of a "init" ``Seq` a` and a "last" `a`. Similar to `:|` for `NonEmpty`, but at the end of the list instead of at the beginning.

Can be used to match on the init and last of an `NESeq`, and also used to construct an `NESeq` by snocing an item to the end of a `Seq`, ensuring that the result is non-empty.

#### Instances

Instances details

MonadZip NESeq Source #

    mzipWith = zipWith

    munzip = unzip

Instance details Defined in Data.Sequence.NonEmpty.Internal Methods mzip :: NESeq a -> NESeq b -> NESeq (a, b) Source # mzipWith :: (a -> b -> c) -> NESeq a -> NESeq b -> NESeq c Source # munzip :: NESeq (a, b) -> (NESeq a, NESeq b) Source #
Foldable1 NESeq Source # |

Instance details

Defined in Data.Sequence.NonEmpty.Internal

Methods

fold1 :: Semigroup m => NESeq m -> m Source #

foldMap1 :: Semigroup m => (a -> m) -> NESeq a -> m Source #

foldMap1' :: Semigroup m => (a -> m) -> NESeq a -> m Source #

toNonEmpty :: NESeq a -> NonEmpty a Source #

maximum :: Ord a => NESeq a -> a Source #

minimum :: Ord a => NESeq a -> a Source #

head :: NESeq a -> a Source #

last :: NESeq a -> a Source #

foldrMap1 :: (a -> b) -> (a -> b -> b) -> NESeq a -> b Source #

foldlMap1' :: (a -> b) -> (b -> a -> b) -> NESeq a -> b Source #

foldlMap1 :: (a -> b) -> (b -> a -> b) -> NESeq a -> b Source #

foldrMap1' :: (a -> b) -> (a -> b -> b) -> NESeq a -> b Source #

Eq1 NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods liftEq :: (a -> b -> Bool) -> NESeq a -> NESeq b -> Bool Source #
Ord1 NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods liftCompare :: (a -> b -> Ordering) -> NESeq a -> NESeq b -> Ordering Source #
Read1 NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (NESeq a) Source # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [NESeq a] Source # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (NESeq a) Source # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [NESeq a] Source #
Show1 NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> NESeq a -> ShowS Source # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [NESeq a] -> ShowS Source #
Comonad NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods extract :: NESeq a -> a Source # duplicate :: NESeq a -> NESeq (NESeq a) Source # extend :: (NESeq a -> b) -> NESeq a -> NESeq b Source #
Applicative NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods pure :: a -> NESeq a Source # (<*>) :: NESeq (a -> b) -> NESeq a -> NESeq b Source # liftA2 :: (a -> b -> c) -> NESeq a -> NESeq b -> NESeq c Source # (*>) :: NESeq a -> NESeq b -> NESeq b Source # (<*) :: NESeq a -> NESeq b -> NESeq a Source #
Functor NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods fmap :: (a -> b) -> NESeq a -> NESeq b Source # (<$) :: a -> NESeq b -> NESeq a Source #
Monad NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods (>>=) :: NESeq a -> (a -> NESeq b) -> NESeq b Source # (>>) :: NESeq a -> NESeq b -> NESeq b Source # return :: a -> NESeq a Source #
MonadFix NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods mfix :: (a -> NESeq a) -> NESeq a Source #
Foldable NESeq Source # | `foldr1`, `foldl1`, `maximum`, and `minimum` are all total, unlike for `Seq`.

Instance details

Defined in Data.Sequence.NonEmpty.Internal

Methods

fold :: Monoid m => NESeq m -> m Source #

foldMap :: Monoid m => (a -> m) -> NESeq a -> m Source #

foldMap' :: Monoid m => (a -> m) -> NESeq a -> m Source #

foldr :: (a -> b -> b) -> b -> NESeq a -> b Source #

foldr' :: (a -> b -> b) -> b -> NESeq a -> b Source #

foldl :: (b -> a -> b) -> b -> NESeq a -> b Source #

foldl' :: (b -> a -> b) -> b -> NESeq a -> b Source #

foldr1 :: (a -> a -> a) -> NESeq a -> a Source #

foldl1 :: (a -> a -> a) -> NESeq a -> a Source #

toList :: NESeq a -> [a] Source #

null :: NESeq a -> Bool Source #

length :: NESeq a -> Int Source #

elem :: Eq a => a -> NESeq a -> Bool Source #

maximum :: Ord a => NESeq a -> a Source #

minimum :: Ord a => NESeq a -> a Source #

sum :: Num a => NESeq a -> a Source #

product :: Num a => NESeq a -> a Source #

Traversable NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods traverse :: Applicative f => (a -> f b) -> NESeq a -> f (NESeq b) Source # sequenceA :: Applicative f => NESeq (f a) -> f (NESeq a) Source # mapM :: Monad m => (a -> m b) -> NESeq a -> m (NESeq b) Source # sequence :: Monad m => NESeq (m a) -> m (NESeq a) Source #
Invariant NESeq Source # | Since: 0.3.4.4
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods invmap :: (a -> b) -> (b -> a) -> NESeq a -> NESeq b Source #
Alt NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods (<!>) :: NESeq a -> NESeq a -> NESeq a Source # some :: Applicative NESeq => NESeq a -> NESeq [a] Source # many :: Applicative NESeq => NESeq a -> NESeq [a] Source #
Apply NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods (<.>) :: NESeq (a -> b) -> NESeq a -> NESeq b Source # (.>) :: NESeq a -> NESeq b -> NESeq b Source # (<.) :: NESeq a -> NESeq b -> NESeq a Source # liftF2 :: (a -> b -> c) -> NESeq a -> NESeq b -> NESeq c Source #
Bind NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods (>>-) :: NESeq a -> (a -> NESeq b) -> NESeq b Source # join :: NESeq (NESeq a) -> NESeq a Source #
Extend NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods duplicated :: NESeq a -> NESeq (NESeq a) Source # extended :: (NESeq a -> b) -> NESeq a -> NESeq b Source #
Traversable1 NESeq Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods traverse1 :: Apply f => (a -> f b) -> NESeq a -> f (NESeq b) Source # sequence1 :: Apply f => NESeq (f b) -> f (NESeq b) Source #
FromJSON a => FromJSON (NESeq a) Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods parseJSON :: Value -> Parser (NESeq a) Source # parseJSONList :: Value -> Parser [NESeq a] Source # omittedField :: Maybe (NESeq a) Source #
ToJSON a => ToJSON (NESeq a) Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods toJSON :: NESeq a -> Value Source # toEncoding :: NESeq a -> Encoding Source # toJSONList :: [NESeq a] -> Value Source # toEncodingList :: [NESeq a] -> Encoding Source # omitField :: NESeq a -> Bool Source #
NFData a => NFData (NESeq a) Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods rnf :: NESeq a -> () Source #
Semigroup (NESeq a) Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods (<>) :: NESeq a -> NESeq a -> NESeq a Source # sconcat :: NonEmpty (NESeq a) -> NESeq a Source # stimes :: Integral b => b -> NESeq a -> NESeq a Source #
Data a => Data (NESeq a) Source # |

Instance details

Defined in Data.Sequence.NonEmpty.Internal

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> NESeq a -> c (NESeq a) Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (NESeq a) Source #

toConstr :: NESeq a -> Constr Source #

dataTypeOf :: NESeq a -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (NESeq a)) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (NESeq a)) Source #

gmapT :: (forall b. Data b => b -> b) -> NESeq a -> NESeq a Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> NESeq a -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> NESeq a -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> NESeq a -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> NESeq a -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> NESeq a -> m (NESeq a) Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> NESeq a -> m (NESeq a) Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> NESeq a -> m (NESeq a) Source #

Read a => Read (NESeq a) Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods readsPrec :: Int -> ReadS (NESeq a) Source # readList :: ReadS [NESeq a] Source # readPrec :: ReadPrec (NESeq a) Source # readListPrec :: ReadPrec [NESeq a] Source #
Show a => Show (NESeq a) Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods showsPrec :: Int -> NESeq a -> ShowS Source # show :: NESeq a -> String Source # showList :: [NESeq a] -> ShowS Source #
Eq a => Eq (NESeq a) Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods (==) :: NESeq a -> NESeq a -> Bool Source # (/=) :: NESeq a -> NESeq a -> Bool Source #
Ord a => Ord (NESeq a) Source # |
Instance details Defined in Data.Sequence.NonEmpty.Internal Methods compare :: NESeq a -> NESeq a -> Ordering Source # (<) :: NESeq a -> NESeq a -> Bool Source # (<=) :: NESeq a -> NESeq a -> Bool Source # (>) :: NESeq a -> NESeq a -> Bool Source # (>=) :: NESeq a -> NESeq a -> Bool Source # max :: NESeq a -> NESeq a -> NESeq a Source # min :: NESeq a -> NESeq a -> NESeq a Source #

## 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 ``IsNonEmpty` n` (where `n` 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, and n is the NESeq
    safeHead IsEmpty                  = 0  -- here the user provided an empty sequence

Matching on ``IsNonEmpty` n` means that the original `Seq` 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 ``IsNonEmpty` n` (where `n` 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 ``Just` n` with an `NESeq`, if the `Seq` was not empty.

`nonEmptySeq` and ``maybe` `empty` `toSeq`` form an isomorphism: they are perfect structure-preserving inverses of eachother.

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 ``maybe` `empty` `toSeq`` form an isomorphism: they are perfect structure-preserving inverses of eachother.

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`. ``withNonEmpty` def f` will take a `Seq`. 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`.

insertSeqAt :: Int -> a -> Seq a -> NESeq a Source #

Turn a `Seq` into a guarantted non-empty `NESeq` by adding an element at a given index.

    insertSeqAt 1 0 (Data.Sequence.fromList [1,2,3]) == fromList (1 :| [0,2,3])

# Construction

singleton :: a -> NESeq a Source #

\( O(1) \). A singleton sequence.

(<|) :: 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.

(|><) :: NESeq a -> Seq a -> NESeq a infixr 5 Source #

\( O(\log(\min(n_1,n_2))) \). Concatenate a non-empty sequence with a potentially empty sequence (`Seq`), to produce a guaranteed non-empty sequence. Mnemonic: like `><`, but a pipe for the guarunteed non-empty side.

(><|) :: Seq a -> NESeq a -> NESeq a infixr 5 Source #

\( O(\log(\min(n_1,n_2))) \). Concatenate a non-empty sequence with a potentially empty sequence (`Seq`), to produce a guaranteed non-empty sequence. Mnemonic: like `><`, but a pipe for the guarunteed non-empty side.

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). ``cycleTaking` k xs` forms a sequence of length `k` 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.

unfoldl :: (b -> (Maybe b, a)) -> b -> NESeq a Source #

``unfoldl` f x` is equivalent to ``reverse` (`unfoldr` (`fmap` swap . f) x)`.

# Deconstruction

Additional functions for deconstructing sequences are available via the `Foldable` instance of `NESeq`.

head :: NESeq a -> a Source #

O(1). Retrieve the left-most item in a non-empty sequence. Note that this function is total.

tail :: NESeq a -> Seq a Source #

O(1). Delete the left-most item in a non-empty sequence. Returns a potentially empty sequence (`Seq`) in the case that the original `NESeq` contained only a single element. Note that this function is total.

last :: NESeq a -> a Source #

O(1). Retrieve the right-most item in a non-empty sequence. Note that this function is total.

init :: NESeq a -> Seq a Source #

O(1). Delete the right-most item in a non-empty sequence. Returns a potentially empty sequence (`Seq`) in the case that the original `NESeq` contained only a single element. Note that this function is total.

## Queries

length :: NESeq a -> Int Source #

\( O(1) \). The number of elements in the sequence.

# Scans

scanl :: (a -> b -> a) -> a -> NESeq b -> NESeq a Source #

`scanl` is similar to `foldl`, but returns a sequence of reduced values from the left:

    scanl f z (fromList [x1, x2, ...]) = fromList [z, z `f` x1, (z `f` x1) `f` x2, ...]

scanl1 :: (a -> a -> a) -> NESeq a -> NESeq a Source #

`scanl1` is a variant of `scanl` that has no starting value argument:

    scanl1 f (fromList [x1, x2, ...]) = fromList [x1, x1 `f` x2, ...]

scanr :: (a -> b -> b) -> b -> NESeq a -> NESeq b Source #

`scanr` is the right-to-left dual of `scanl`.

scanr1 :: (a -> a -> a) -> NESeq a -> NESeq a Source #

`scanr1` is a variant of `scanr` that has no starting value argument.

# 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.

``takeWhileR` p xs` is equivalent to ``reverse` (`takeWhileL` p (`reverse` xs))`.

dropWhileL :: (a -> Bool) -> NESeq a -> Seq a Source #

\( O(i) \) where \( i \) is the prefix length. ``dropWhileL` p xs` returns the suffix remaining after ``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. ``dropWhileR` p xs` returns the prefix remaining after ``takeWhileR` p xs`.

Returns a possibly empty sequence (`Seq`) in the case that the predicate passes for all items.

``dropWhileR` p xs` is equivalent to ``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:

- ``This` ys` means that the predicate was true for all items, and `ys` is the entire original sequence.
- ``That` zs` means that the predicate failed on the first item, and `zs` is the entire original sequence.
- ``These` ys zs` gives `ys` (the prefix of elements that satisfy the predicae) and `zs` (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:

- ``This` ys` means that the predicate was true for all items, and `ys` is the entire original sequence.
- ``That` zs` means that the predicate failed on the first item, and `zs` is the entire original sequence.
- ``These` ys zs` gives `ys` (the suffix of elements that satisfy the predicae) and `zs` (the remainder of the sequence, before the suffix)

breakl :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a) Source #

\( O(i) \) where \( i \) is the breakpoint index.

``breakl` p` is ``spanl` (not . p)`.

breakr :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a) Source #

\( O(i) \) where \( i \) is the breakpoint index.

``breakr` p` is ``spanr` (not . p)`.

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`:

- ``This` ys` means that the predicate was true for all items, and `ys` is the entire original sequence.
- ``That` zs` means that the predicate failed on the first item, and `zs` is the entire original sequence.
- ``These` ys zs` gives `ys` (the sequence of elements for which the predicate was true) and `zs` (the sequence of elements for which the predicate was false).

filter :: (a -> Bool) -> NESeq a -> Seq a Source #

\( O(n) \). The `filter` function takes a predicate `p` and a sequence `xs` and returns a sequence of those elements which satisfy the predicate.

Returns a potentially empty sequence (`Seq`) in the case that the predicate fails for all items in the sequence.

# 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. ``sortOn` f` is equivalent to ``sortBy` (`compare` ``on`` f)`, but has the performance advantage of only evaluating `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`), ``sortBy` (`compare` ``on`` f)` will be faster than ``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. ``unstableSortOn` f` is equivalent to ``unstableSortBy` (`compare` ``on`` f)`, but has the performance advantage of only evaluating `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`), ``unstableSortBy` (`compare` ``on`` f)` will be faster than ``unstableSortOn` f`.

# Indexing

lookup :: Int -> NESeq 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`.

Unlike `index`, this can be used to retrieve an element without forcing it.

(!?) :: 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, ``take` i s` yields the empty sequence. If the sequence contains fewer than `i` 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, ``drop` i s` yields the whole sequence. If the sequence contains fewer than `i` elements, the empty sequence is returned.

insertAt :: Int -> a -> NESeq a -> NESeq a Source #

\( O(\log(\min(i,n-i))) \). ``insertAt` i x xs` inserts `x` 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.

- ``This` ys` means that the given position was longer than the length of the list, and `ys` is the entire original system.
- ``That` zs` means that the given position was zero or smaller, and so `zs` is the entire original sequence.
- ``These` ys zs` gives `ys` (the sequence of elements before the given position, `take n xs`) and `zs` (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 #

``findIndexL` p xs` finds the index of the leftmost element that satisfies `p`, if any exist.

findIndicesL :: (a -> Bool) -> NESeq a -> [Int] Source #

``findIndicesL` p` finds all indices of elements that satisfy `p`, in ascending order.

findIndexR :: (a -> Bool) -> NESeq a -> Maybe Int Source #

``findIndexR` p xs` finds the index of the rightmost element that satisfies `p`, if any exist.

findIndicesR :: (a -> Bool) -> NESeq a -> [Int] Source #

``findIndicesR` p` finds all indices of elements that satisfy `p`, in descending order.

# Folds

General folds are available via the `Foldable` instance of `Seq`.

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.

reverse :: NESeq a -> NESeq a Source #

\( O(n) \). The reverse of a sequence.

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.

zipWith :: (a -> b -> c) -> NESeq a -> NESeq b -> NESeq c Source #

\( 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.

zip3 :: NESeq a -> NESeq b -> NESeq c -> NESeq (a, b, c) Source #

\( O(\min(n_1,n_2,n_3)) \). `zip3` takes three sequences and returns a sequence of triples, analogous to `zip`.

zipWith3 :: (a -> b -> c -> d) -> NESeq a -> NESeq b -> NESeq c -> NESeq d Source #

\( 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`.

zip4 :: NESeq a -> NESeq b -> NESeq c -> NESeq d -> NESeq (a, b, c, d) Source #

\( O(\min(n_1,n_2,n_3,n_4)) \). `zip4` takes four sequences and returns a sequence of quadruples, analogous to `zip`.

zipWith4 :: (a -> b -> c -> d -> e) -> NESeq a -> NESeq b -> NESeq c -> NESeq d -> NESeq e Source #

\( 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`.

unzip :: NESeq (a, b) -> (NESeq a, NESeq b) Source #

Unzip a sequence of pairs.

    unzip ps = ps `seq` (fmap fst ps) (fmap snd ps)

Example:

    unzip $ fromList ((1,"a") :| [(2,"b"), (3,"c")]) =
      (fromList (1:|[2,3]), fromList ("a":|["b","c"]))

See the note about efficiency at `unzipWith`.

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.