MkSTSequence functorfunctor MkSTSequence (structure Seq :
SEQUENCE) :>
ST_SEQUENCE
where Seq = Seq
Implements single-threaded sequences with an underlying mutable array and a history. Every single-threaded sequence is either current or old, depending upon whether or not it has ever been updated. When a single-threaded sequence is current, updates can proceed efficiently on the mutable array, returning a new single-threaded sequence which is current, and modifying the original sequence to be old. When a single-threaded sequence is old, all operations are expensive, and are not considered by the cost semantics given below. In particular, they must build a new array from the history, which costs at least as much as the size of the history.
As long as operations are always performed on a current single-threaded sequence, they are effficient.
ST_SEQUENCE Cost SpecificationsThe following costs assume that all single-threaded sequences are a current version.
| Work | Span | |
nth $S\ i$
|
\[O(1)\] | \[O(1)\] |
update $(S, (i, x))$ |
\[O(1)\] | \[O(1)\] |
inject $(S, U)$ |
\[O(|U|)\] | \[O(1)\] |
The following costs assumes Seq =
ArraySequence.
| Work | Span | |
fromSeq $S$toSeq $S$
|
\[O(|S|)\] | \[O(1)\] |