The MkSTSequence functor

« 210 Library Documentation

Overview

functor MkSTSequence(structure Seq : SEQUENCE) : ST_SEQUENCE

Implements ST_SEQUENCE with a state ref and history. If the state is CUR a, then the single-threaded sequence is current and $a$ can be accessed immediately. Otherwise, if the state is MOD, the single-threaded sequence needs to be reconstructed from history — that is, by sequentially applying every update to the original sequence from which the single-threaded sequence was created.

ST_SEQUENCE Cost Specifications

Work Span
nth $ST\:i$
update $(i,v)\:ST$ 		\[O(1)\] \[O(1)\]
inject $I\:ST$ \[O(|I|)\] \[O(1)\]
fromSeq $S$
toSeq $ST$ 		\[O(|S|)\] \[O(1)\]