Data.Sequence.NonEmpty.Internal

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 Data.Seq.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.

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.

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.

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

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 Data.Sequence.NonEmpty.IsNotEmpty pattern.

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

O(1) . A singleton sequence.

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

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.

O(n) . Convert a given sequence length and a function representing that sequence into a sequence.

O(\log n) . replicate n x is a sequence consisting of n copies of x. Is only defined when n is positive.

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.

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(1) . Add an element to the left end of a non-empty sequence. Mnemonic: a triangle with the single element at the pointy end.

O(\log(\min(n_1,n_2))) . Concatenate two non-empty sequences.

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.

Defined here but hidden; intended for use with RULES pragma.

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.

O(n). traverseWithIndex1 is a version of traverse1 that also offers access to the index of each element.

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.

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.

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.