ArraySequence structurestructure ArraySequence
:> SEQUENCE
Implements the SEQUENCE
interface with
type α t = α
ArraySlice.slice
nth and subseq.
When $|s| \geq 2$, splitMid s
is logically equivalent to
PAIR (take s (n div 2), drop s (n div 2))
SEQUENCE Cost Specifications| Work | Span | |
nth $S\ i$length $S$empty ()singleton $x$
|
\[O(1)\] | \[O(1)\] |
subseq $S\ (i, \ell)$take $S\ n$drop $S\ n$
|
\[O(1)\] | \[O(1)\] |
splitHead $S$splitMid $S$
|
\[O(1)\] | \[O(1)\] |
toList $S$ |
\[O(|S|)\] | \[O(|S|)\] |
fromList $L$
|
\[O(|L|)\] | \[O(|L|)\] |
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 $(A, B)$ |
\[O(|A|+|B|)\] | \[O(1)\] |
flatten $S$ |
\[O\left(\sum_{x \in S} \left(1 + |x| \right) \right)\] | \[O(\log|S|)\] |
filter $p\ S$filterIdx $p\ S$
|
\[\sum_{x \in S} \mathcal{W}(p(x))\] | \[O(\log|S|) + \max_{x \in S} \mathcal{S}(p(x))\] |
map $f\ S$mapIdx $f\ S$
|
\[\sum_{x \in S} \mathcal{W}(f(x))\] | \[\max_{x \in S} \mathcal{S}(f(x))\] |
zipWith $f\ (A, B)$ |
\[\sum_{i=0}^{\min(|A|,|B|)-1} \mathcal{W}(f(A_i, B_i))\] | \[\max_{i=0}^{\min(|A|,|B|)-1} \mathcal{S}(f(A_i, B_i))\] |
zip $(A, B)$ |
\[O(\min(|A|,|B|))\] | \[O(1)\] |
update $(S, (i, x))$ |
\[O(|S|)\] | \[O(1)\] |
inject $(S, U)$ |
\[O(|S|+|U|)\] | \[O(1)\] |
iterate $f\ b_0\ S$iteratePrefixes $f\ b_0\ S$iteratePrefixesIncl $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))\] |
The following costs assume that the work
and span of cmp are constant.
| Work | Span | |
sort cmp $S$collect cmp $S$
|
\[O(|S|\log|S|)\] | \[O(\log^2|S|)\] |
merge cmp $(A, B)$ |
\[O(|A| + |B|)\] | \[O(\log(|A| + |B|))\] |
collate cmp $(A, B)$ |
\[O(|A| + |B|)\] | \[O(\log(\min(|A|, |B|)))\] |
argmax cmp $S$ |
\[O(|S|)\] | \[O(\log|S|)\] |
The following costs assume the work and span of $f$ are constant.
If this is not the case, then refer directly to the implementations of
reduce, scan, and scanIncl.
| Work | Span | |
reduce $f\ b\ S$scan $f\ b\ S$scanIncl $f\ b\ S$
|
\[O(|S|)\] | \[O(\log |S|)\] |