package lwd

  1. Overview
  2. Docs

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.

type 'a t = private 'a seq

Type of balanced sequences

val empty : 'a t
val element : 'a -> 'a t
val concat : 'a t -> 'a t -> 'a t
val view : 'a t -> ('a, 'a t) view
OCaml

Innovation. Community. Security.