package lwd

A variant of the sequence type that guarantees that the depth of a transformation, measured as the number of nested concat nodes, grows in O(log n) where n is the number of elements in the sequnce.

This is useful to prevent stack overflows and to avoid degenerate cases where a single element changes, but it is at the end of a linear sequence of concat nodes, thus making the total work O(n). For instance, in:

concat e1 (concat e2 (concat e3 (... (concat e_n))...))

If e_n changes, the whole spine has to be recomputed.

Using Balanced.concat, the representation will be re-balanced internally. Then Balanced.view should be used to access the balanced sequence.

When working with balanced sequences in a transformation pipeline, it is only useful to balance the first sequence of the pipeline. Derived sequence will have a depth bounded by the depth of the first one.