# The ListSequence structure

## Overview

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.