The ListSequence structure

« 210 Library Documentation


structure 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.