ArraySequence structureImplements
SEQUENCE with
type 'a seq = { ary : 'a array, idx : int, len : int }
SEQUENCE Cost Specifications| Work | Span | |
nth $S\:i$length $S$ |
\[O(1)\] | \[O(1)\] |
toList $S$fromList $S$ |
\[O(|S|)\] | \[O(|S|)\] |
tabulate $f\:n$ |
\[\sum_{i=0}^{n-1} \mathcal{W}(f(i))\] | \[\max_{i=0}^{n-1} \mathcal{S}(f(i))\] |
rev $S$enum $S$ |
\[O(|S|)\] | \[O(1)\] |
append $(S_1, S_2)$ |
\[O(|S_1|+|S_2|)\] | \[O(1)\] |
flatten $S$ |
\[O(|S|) + \sum_{e\in S} O(|e|)\] | \[O(\log|S|)\] |
filter $p\:S$filterIdx $p\:S$ |
\[\sum_{e\in S} \mathcal{W}(p(e))\] | \[O(\log|S|) + \max_{e\in S} \mathcal{S}(p(e))\] |
map $f\:S$mapIdx $f\:S$ |
\[\sum_{e\in S} \mathcal{W}(f(e))\] | \[\max_{e\in S} \mathcal{S}(f(e))\] |
map2 $f\:S_1\:S_2$ |
\[\sum_{i=0}^{\min(|S_1|,|S_2|)-1} \mathcal{W}(f(S_{1i},S_{2i}))\] | \[\max_{i=0}^{\min(|S_1|,|S_2|)-1} \mathcal{S}(f(S_{1i},S_{2i}))\] |
zip $S_1\:S_2$ |
\[O(\min(|S_1|,|S_2|))\] | \[O(1)\] |
inject $I\:S$ |
\[O(|I|+|S|)\] | \[O(1)\] |
subseq $S\:(i, len)$ |
\[O(1)\] | \[O(1)\] | take $(S, n)$drop $(S, n)$ |
\[O(1)\] | \[O(1)\] |
showl $S$showt $S$ |
\[O(1)\] | \[O(1)\] |
iter $f\:b_0\:S$iterh $f\:b_0\:S$ |
\[\sum_{i=0}^{|S|-1} \mathcal{W}(f(b_i, S_i))\] | \[\sum_{i=0}^{|S|-1} \mathcal{S}(f(b_i, S_i))\] |
For reduce,
$\mathcal{O}_r(f,b,S)$ represents the
set of applications of $f$ as defined in the
SEQUENCE
specification. For scan,
$\mathcal{O}_s(f,b,S)$ represents the
set of applications of $f$ as defined by the implementation
of scan in lecture.
| Work | Span | |
reduce $f\:b\:S$ |
\[O(|S|)+\sum_{f(x,y)\in\mathcal{O}_r(f,b,S)} \mathcal{W}(f(x,y))\] | \[O\left(\log|S|\max_{f(x,y)\in\mathcal{O}_r(f,b,S)} \mathcal{S}(f(x,y))\right)\] |
scan $f\:b\:S$scani $f\:b\:S$ |
\[O(|S|)+\sum_{f(x,y)\in\mathcal{O}_s(f,b,S)} \mathcal{W}(f(x,y))\] | \[O\left(\log|S|\max_{f(x,y)\in\mathcal{O}_s(f,b,S)} \mathcal{S}(f(x,y))\right)\] |
The following costs assume that the work and span of the application of $cmp$ is constant.
| Work | Span | |
sort $cmp\:S$collect $cmp\:S$ |
\[O(|S|\log|S|)\] | \[O(\log^2|S|)\] |
merge $cmp\:S_1\:S_2$ |
\[O(|S_1|+|S_2|)\] | \[O(\log(|S_1|+|S_2|))\] |
collate $cmp\:(S_1, S_2)$ |
\[O(|S_1|+|S_2|)\] | \[O(\log(\min(|S_1|, |S_2|)))\] |
argmax $cmp\:S$ |
\[O(|S|)\] | \[O(\log|S|)\] |