Menu
We describe a concrete data structure, called a sequence-tree, that represents sequences of arbitrary elements, along with associated algorithms that allow single element access and assignment, subsequence extraction (slicing), and concatenation to be done in logarithmic time relative to sequence length. These operations are functional, in the sense that they leave their operand sequences unchanged. For a single sequence, space is linear in the sequence length. Where a set of multiple sequences have been computed by these algorithms, space may be sublinear, because of node sharing. Sequence-trees use immutable, shared, dynamically allocated nodes and thus may require garbage collection, if some of the sequences in a set are abandoned. However, the interconnection of nodes is non-cyclic, so explicitly programmed collection using reference counting is reasonable, should a general-purpose garbage collector be unavailable. Other sequence representations admit only to linear-time algorithms for one or more of the aforementioned operations. Thus sequence-trees give improved performance in applications where all the operations are needed.