ArraySequence structurestructure ArraySequence
:> SEQUENCE
Implements sequences with
type α t = α
ArraySlice.slice
ArraySequence-Specific Behavior
(splitMid
s) splits $s$ exactly in half when $|s| \geq 2$. The right half gets
an extra element when $|s|$ is odd.
SEQUENCE Cost Specifications| Work | Span | |
nth $S\ i$length $S$empty ()singleton $x$
|
O(1) | O(1) |
toList $S$ |
O(|S|) | O(|S|) |
fromList $L$
|
O(|L|) | O(|L|) |
tabulate $f\ n$ |
n−1∑i=0W(f(i)) | max |
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) |
subseq $S\ (i, \ell)$take $S\ n$drop $S\ n$
|
O(1) | O(1) |
splitHead $S$splitMid $S$
|
O(1) | 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|) |