# The ArraySequence structure

## Overview

structure 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$ $\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)$ 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|)$