The ArraySequence structure

« 210 Library Documentation

Overview

structure ArraySequence :> SEQUENCE

Implements the SEQUENCE interface with

type α t = α ArraySlice.slice
This permits constant-time implementations of a number of crucical operations such as nth and subseq.

Implementation-Defined Behavior

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|)\]