# The ArraySequence structure

## Overview

Implements SEQUENCE with

type 'a seq = { ary : 'a array, idx : int, len : int } 
where the sequence is implicitly defined as starting at $ary[idx]$ with length $len$.

## SEQUENCE Cost Specifications

 Work Span nth $S\:i$ length $S$ $O(1)$ $O(1)$ toList $S$ fromList $S$ $O(|S|)$ $O(|S|)$ 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 $(S_1, S_2)$ $O(|S_1|+|S_2|)$ $O(1)$ flatten $S$ $O(|S|) + \sum_{e\in S} O(|e|)$ $O(\log|S|)$ filter $p\:S$ filterIdx $p\:S$ $\sum_{e\in S} \mathcal{W}(p(e))$ $O(\log|S|) + \max_{e\in S} \mathcal{S}(p(e))$ map $f\:S$ mapIdx $f\:S$ $\sum_{e\in S} \mathcal{W}(f(e))$ $\max_{e\in S} \mathcal{S}(f(e))$ map2 $f\:S_1\:S_2$ $\sum_{i=0}^{\min(|S_1|,|S_2|)-1} \mathcal{W}(f(S_{1i},S_{2i}))$ $\max_{i=0}^{\min(|S_1|,|S_2|)-1} \mathcal{S}(f(S_{1i},S_{2i}))$ zip $S_1\:S_2$ $O(\min(|S_1|,|S_2|))$ $O(1)$ inject $I\:S$ $O(|I|+|S|)$ $O(1)$ subseq $S\:(i, len)$ $O(1)$ $O(1)$ take $(S, n)$ drop $(S, n)$ $O(1)$ $O(1)$ showl $S$ showt $S$ $O(1)$ $O(1)$ iter $f\:b_0\:S$ iterh $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))$

For reduce, $\mathcal{O}_r(f,b,S)$ represents the set of applications of $f$ as defined in the SEQUENCE specification. For scan, $\mathcal{O}_s(f,b,S)$ represents the set of applications of $f$ as defined by the implementation of scan in lecture.

 Work Span reduce $f\:b\:S$ $O(|S|)+\sum_{f(x,y)\in\mathcal{O}_r(f,b,S)} \mathcal{W}(f(x,y))$ $O\left(\log|S|\max_{f(x,y)\in\mathcal{O}_r(f,b,S)} \mathcal{S}(f(x,y))\right)$ scan $f\:b\:S$ scani $f\:b\:S$ $O(|S|)+\sum_{f(x,y)\in\mathcal{O}_s(f,b,S)} \mathcal{W}(f(x,y))$ $O\left(\log|S|\max_{f(x,y)\in\mathcal{O}_s(f,b,S)} \mathcal{S}(f(x,y))\right)$

The following costs assume that the work and span of the application of $cmp$ is constant.

 Work Span sort $cmp\:S$ collect $cmp\:S$ $O(|S|\log|S|)$ $O(\log^2|S|)$ merge $cmp\:S_1\:S_2$ $O(|S_1|+|S_2|)$ $O(\log(|S_1|+|S_2|))$ collate $cmp\:(S_1, S_2)$ $O(|S_1|+|S_2|)$ $O(\log(\min(|S_1|, |S_2|)))$ argmax $cmp\:S$ $O(|S|)$ $O(\log|S|)$