# The MkSTSequence functor

## 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)$