A newtype wrapper around a FingerTree, representing a finger tree 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.FingerTree functions while forcing the provided value to WHNF.

Convert a FingerTree into a StrictFingerTree by forcing each element to WHNF.

O(1). The empty sequence.

O(1). A singleton sequence.

O(1). Add an element to the left end of a sequence. Mnemonic: a triangle with the single element at the pointy end.

O(1). Add an element to the right end of a sequence. Mnemonic: a triangle with the single element at the pointy end.

O(log(min(n1,n2))). Concatenate two sequences.

O(n). Create a sequence from a finite list of elements. The opposite operation toList is supplied by the Foldable instance.

O(1). Is this the empty sequence?

O(1). Analyse the left end of a sequence.

O(1). Analyse the right end of a sequence.

A result of search, attempting to find a point where a predicate on splits of the sequence changes from False to True.

Since: 0.1.2.0

O(log(min(i,n-i))). Search a sequence for a point where a predicate on splits of the sequence changes from False to True.

The argument p is a relation between the measures of the two sequences that could be appended together to form the sequence t. If the relation is False at the leftmost split and True at the rightmost split, i.e.

not (p mempty (measure t)) && p (measure t) mempty

then there must exist an element x in the sequence such that p is False for the split immediately before x and True for the split just after it:

In this situation, search p t returns such an element x and the pieces l and r of the sequence to its left and right respectively. That is, it returns Position l x r such that

• l >< (x <| r) = t

• not (p (measure l) (measure (x <| r))

• p (measure (l |> x)) (measure r)

For predictable results, one should ensure that there is only one such point, i.e. that the predicate is monotonic on t.

Since: 0.1.2.0

O(log(min(i,n-i))). Split a sequence at a point where the predicate on the accumulated measure of the prefix changes from False to True.

For predictable results, one should ensure that there is only one such point, i.e. that the predicate is monotonic.

O(log(min(i,n-i))). Given a monotonic predicate p, takeUntil p t is the largest prefix of t whose measure does not satisfy p.

• takeUntil p t = fst (split p t)

O(log(min(i,n-i))). Given a monotonic predicate p, dropUntil p t is the rest of t after removing the largest prefix whose measure does not satisfy p.

• dropUntil p t = snd (split p t)

O(n). The reverse of a sequence.

Like fmap, but with constraints on the element types.

Like fmap, but safe only if the function preserves the measure.

Things that can be measured.

View of the left end of a sequence.

View of the right end of a sequence.