ListSequence structurestructure ListSequence
:> SEQUENCE
where type α t = α list
ListSequence-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$ |
\[O(i)\] | \[O(i)\] |
empty ()singleton $x$toList $S$fromList $L$
|
\[O(1)\] | \[O(1)\] |
tabulate $f\ n$ |
\[\sum_{i=0}^{n-1} \mathcal{W}(f(i))\] | \[\sum_{i=0}^{n-1} \mathcal{S}(f(i))\] |
length $S$rev $S$enum $S$
|
\[O(|S|)\] | \[O(|S|)\] |
append $(A, B)$ |
\[O(|A|)\] | \[O(|A|)\] |
flatten $S$ |
\[O\left(\sum_{x \in S} \left(1 + |x| \right) \right)\] | \[O\left(\sum_{x \in S} \left(1 + |x| \right) \right)\] |
filter $p\ S$filterIdx $p\ S$
|
\[\sum_{x \in S} \mathcal{W}(p(x))\] | \[\sum_{x \in S} \mathcal{S}(p(x))\] |
map $f\ S$mapIdx $f\ S$
|
\[\sum_{x \in S} \mathcal{W}(f(x))\] | \[\sum_{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))\] | \[\sum_{i=0}^{\min(|A|,|B|)-1} \mathcal{S}(f(A_i, B_i))\] |
zip $(A, B)$ |
\[O(\min(|A|,|B|))\] | \[O(\min(|A|,|B|))\] |
update $(S, (i, x))$ |
\[O(i)\] | \[O(i)\] |
inject $(S, U)$ |
\[O\left(\sum_{(i,x) \in U} i \right)\] | \[O\left(\sum_{(i,x) \in U} i \right)\] |
subseq $S\ (i, \ell)$
|
\[O(i + \ell)\] | \[O(i + \ell)\] |
take $S\ n$drop $S\ n$
|
\[O(n)\] | \[O(n)\] |
splitHead $S$
|
\[O(1)\] | \[O(1)\] |
splitMid $S$
|
\[O(|S|)\] | \[O(|S|)\] |
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(|S|)\] |
merge cmp $(A, B)$ |
\[O(|A| + |B|)\] | \[O(|A| + |B|)\] |
collate cmp $(A, B)$ |
\[O(|A| + |B|)\] | \[O(|A| + |B|)\] |
argmax cmp $S$ |
\[O(|S|)\] | \[O(|S|)\] |
For the costs of reduce, scan, and
scanIncl, refer directly to their implementations.