ArraySequence structurestructure ArraySequence
:> SEQUENCE
Implements the SEQUENCE
interface with
type α t = α
ArraySlice.slice
nth and subseq.
When |s|≥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 ilength Sempty ()singleton x
|
O(1) | O(1) |
subseq S (i,ℓ)take S ndrop S n
|
O(1) | O(1) |
splitHead SsplitMid S
|
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 Senum 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\ SfilterIdx p\ S
|
\sum_{x \in S} \mathcal{W}(p(x)) | O(\log|S|) + \max_{x \in S} \mathcal{S}(p(x)) |
map f\ SmapIdx 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\ SiteratePrefixes f\ b_0\ SiteratePrefixesIncl 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 Scollect 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\ Sscan f\ b\ SscanIncl f\ b\ S
|
O(|S|) | O(\log |S|) |