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 StoSeq S
|
O(|S|) | O(1) |