A representation of a sequence of values of type a, allowing access to the ends in constant time, and append and split in time logarithmic in the size of the smaller piece.

A variety of abstract data types can be implemented by using different element types and measurements.

Things that can be measured.

O(1). The empty sequence.

O(1). A singleton sequence.

The fromList function constructs the structure l from the given list of Item l

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

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.

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.

Map all elements of the tree with a function that also takes the measure of the prefix of the tree to the left of the element.

Map all elements of the tree with a function that also takes the measure of the prefix to the left and of the suffix to the right of the element.

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

Like traverse, but with constraints on the element types.

Traverse the tree from left to right with a function that also takes the measure of the prefix of the tree to the left of the element.

Traverse the tree from left to right with a function that also takes the measure of the prefix to the left and the measure of the suffix to the right of the element.

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