Round 2: sequences and views
The normative CP Lang 0.3 specification.
This is the normative specification (source). For a gentler introduction, start with the guides.
Built on round 1: arrays are [D]T, ranges are runs of a domain with cut
ends, .first/.last are optional.
Key decisions
- Generators are the only iterator.
-> yields T, nonext(); values are pushed into the loop body, so they compile to the hand-written loop.break/returnwork through them; lockstep isList(g). (R07.1.1) - Six capabilities.
Seqwalks;Keyedwalks(key, x);Sizedhas O(1).len;Bidirwalks backwards;Indexedadds O(1)s[i]and.keys;IndexedMutmakess[i]a place (POWERS W4). Adapters keepIndexedwhen they can stay O(1) (slices,.rev,map,take/drop,zip);filter,take_whileand generators areSeq. (R07.1.2) - Laziness is explicit. A chain reruns on every walk. Allocation happens
only at
.collect(), a comprehension orList(...). Lint flags a chain walked twice (sharper when it holds amutlend) and side-effecting closures. (R07.1.3) - Identity everywhere. Every slice keeps its source's keys
(
a[l..=r][i] == a[i],s[2..5][3] == s[3]), and library functions answer in the keys they were given.first,nth(k)andrebasecover relative access. (R07.1.4) - Views are lent values with the rules of
mut a[i]. A value built from a lent part is lent; no lifetime annotations. It is kept only where R05.7.8 to R05.7.10 allow (storage that dies before its sources) and returned only by a fn declaredlends. In-place verbs work on views (a[l..=r].sort()); each has a copying twin (sorted). (R07.1.5) - Prefix scans are indexed by cuts.
pre[c]folds left ofc;pre[v]folds throughv. (R07.1.6) - Costs show. O(1) things are getters or views, allocation is named,
options are named arguments (
max(by:)), and there is no overloading. (R07.1.7)
Terms
Every word below means one thing in this doc, in the stubs and in errors.
| Term | Means | Owns its elements? | Examples |
|---|---|---|---|
sequence (Seq<T>) | anything a for can walk, in order | either | everything in this table (R07.2.1) |
indexed sequence (Indexed<K, T>) | a sequence that also has O(1) s[k], .keys and .len | either | [V]T, List<T>, Str, ranges, slices, .rev (R07.2.2) |
| key | what an indexed sequence is indexed by: a domain position (V) or an Int offset (List, Str) | i: V, 3 (R07.2.3) | |
| collection | a sequence that owns its elements; making one allocates | yes | [V]T arrays, List, Str, Set, Map (R07.2.4) |
| range | a run of a domain, l..r; a sequence of positions or cuts with no data behind it (round 1) | nothing to own | l..=r, ..i, V.range (R07.2.5) |
| view | a sequence made from a source without copying it: O(1) to make, borrows the source, does its work as you walk or read it. Formally, a Seq built from a lent source, so it is a lent value (POWERS W4); there is no View trait and no marker on the struct | no | a[l..=r], a.rev, a.map(f), a.filter(p) (R07.2.6) |
| slice | the view a[r]: one contiguous range r of an indexed source | no | a[l..=r], s[i..], grid[r] (a row) (R07.2.7) |
| adapter | a method that turns a sequence into a view | .map, .filter, .rev, .take, zip (R07.2.8) | |
| chain | adapters applied one after another; still a view, still lazy | no | a.filter(p).map(f) (R07.2.9) |
| generator | a fn declared -> yields T; calling it gives a sequence that reruns the body on each walk | no | divisors(n), dfs(g, s) (R07.2.10) |
| materialize | copy a sequence into a new collection: the only allocation step | .collect(), List(s), [f(x) for x in s] (R07.2.11) | |
| place | something assignable: an element or a mut view | a[i], mut a[l..r] (R07.2.12) |
How they relate:
- Two capabilities. A view is indexed when its adapter can answer
w[k]in O(1): slices,.rev,.map,.items,zip,take/drop. It is only a sequence (walk-only) otherwise:filter,take_while,chain, generators. (R07.2.13) - Slices are the views that narrow keys. Every other indexed view keeps its source's keys unchanged. (R07.2.14)
- Ranges are indexed sequences but not views: they have no source. Slicing with a range gives a view. (R07.2.15)
- Lazy means a view or generator. Its work happens at each walk or read, never up front. Materializing is the only step that does the work once and keeps the result. (R07.2.16)
a[l..=r] // view of a over l..=r; a[l..=r][i] is a[i], i must be in l..=r
s[2..5] // keeps keys: s[2..5][3] is s[3]; s[2..5].nth(0) is s[2]
a[l..=r].keys // l..=r
a.rev // walks a backwards; a.rev[i] is still a[i]
a.map(f) // Indexed<D, U>: (a.map(f))[i] is f(a[i]), O(1) per read
a.items // (i, a[i]) pairs with a's own indicesThe capabilities
| Capability | What it guarantees | Examples |
|---|---|---|
Seq<T> | for x in s walks it in order; each for runs it from the start | generators, s.filter(p), chain(a, b), g[u] (R07.3.1) |
Keyed<D, T> | Seq + s.items walks (key, x); keys survive filter | everything Indexed, s.filter(p), s.take_while(p), Map, g.keyed(), g.keyed(by: f) (R07.3.2) |
Sized | O(1) s.len | collections, ranges, Indexed views, sets, maps (R07.3.3) |
Bidir<T> | s.rev walks backwards; s.last is O(1) | everything Indexed, sorted sets, deques, filter over a Bidir (R07.3.4) |
Indexed<D, T> | Keyed + Sized + Bidir + s[i] for i: D in O(1), s.keys: Range<D> | [D]T, List<T> and Str (D = Int), ranges, slices, .rev, .map(f), zip(a, b) (R07.3.5) |
IndexedMut<D, T> | Indexed + s[i] is a place: sort(), swap, slice assignment | [D]T, List, Str, mut slices (R07.3.6) |
Cost rule. Views are O(1) to make and allocate nothing. A
loop over them compiles to the loop you would write by hand. Anything that
builds a container says so: a comprehension, List(s), or a method named
for its result (sorted, tally, scan).
Slices: which keys survive
Identity everywhere (decision 143; worked through in 04b-keys.md): an
index names the same element everywhere it is valid. A slice narrows the
valid keys and never renames them, for domain arrays, List and Str
alike, so an index taken from a view is valid on the source.
let w = a[l..=r]
let best = w.argmax()! // a position of a, usable anywhere
for (i, x) in w.items: ... // i runs l..=r, not 0..
s[2..5][3] // s[3]; s[2..5][0] traps
w.first!, w.nth(k) // first element; k steps from the start
let t = w.rebase // O(1) view keyed by a fresh 0..w.len domain t.Idx- Keys in, keys out. Library functions answer in the keys they were
given:
s[l..].search(c)is a key ofs,z_function(s[l..])is keyed byl..,a[l..r].scan(+)bya's cuts. Lengths and counts stayInt. (R07.4.1) - Combining two sequences pairs them by walk order:
==,<,starts_with,+, slice assignment andzip. (R07.4.2) [s.keys]xis a table over exactlys's keys;t.rekey(r)re-keys equal-length cells ontorin O(1). (R07.4.3)- Materializing counts from 0:
.collect(),.sorted(),List(w)andStr(w)build a new sequence keyed from 0. To keepw's keys, build a table over them:[w.keys] k => w[k](see R04b.1.6). (R07.4.4) - Lints: a literal index into a slice (
w[0]), and a 0-based counter used as a slice key (for k in 0..w.len: w[k]); both suggestfirst,nth,itemsorrebase. An out-of-keys read traps naming the slice's keys. A rawIntinto a domain slice is a compile error. (R07.4.5)
| View | Indexed by | Walks | Cost |
|---|---|---|---|
a[r] (r: Range<D>; a[j..i] with cut ends is the piece) | D, only inside r | r in order | O(1) (R07.4.6) |
a.rev | D | backwards | O(1) (R07.4.7) |
a.items | D, gives (i, a[i]) | in order | O(1) (R07.4.8) |
a.map(f) | D, gives f(a[i]), calling f on every read | in order | O(1); f per read (R07.4.9) |
zip(a, b) | a's keys, pairing by walk order: the k-th of a with the k-th of b | in order | O(1) (R07.4.10) |
w.drop(k), w.take(k), w.drop_last(k), w.take_last(k) | same as w, clamped: w.drop(k) is w[w.l.next(k) ?? w.r..] | in order | O(1) (R07.4.11) |
grid[r] | the column domain: row r of a [R, C]T | in order | O(1) (R07.4.12) |
grid[rs, cs] | (R, C) pairs inside rs × cs; .items gives ((x, y), v) | row-major | O(1) (R07.4.13) |
zip pairs by walk order and is keyed by its first argument; zipping a
[V]T with an [E]T is still a type error. It stops at the shorter side.
Writing a sequence into a range is slice assignment, not a zip:
q[start..] = suffix copies in order, O(k), and traps in every build if the
lengths differ.
A view borrows its source. Through a var source a view is writable and
every in-place verb works on it: a[l..r].sort(), a[l..=r].reverse(),
a[r].fill(0). Changing the source's length while a view is alive is a
compile error (§128).
Under the hood
A view is a plain library struct built from a lent source: a reference plus the two end cuts as Ints. Direction and adapters are in the type, so nothing is decided at run time and nothing allocates.
a[l..=r] // Slice{src: &a, lo: Int(l.l), hi: Int(r.r)}
a[l..=r].rev.map(f) // Mapped<Rev<Slice<[V]T>>, F>, F the lambda's own type| Written | Lowers to |
|---|---|
a[l..=r], .rev, .map(f) | build the struct, O(1) (R07.5.1) |
w[i] | debug: check lo <= i < hi; then a[i] (no offset: indices are kept) (R07.5.2) |
w.rev[i] | a[i]; only the walk order differs (R07.5.3) |
a.map(f)[i] | f(a[i]), inlined, per read (R07.5.4) |
for x in w | for (i = lo; i < hi; ++i) body(a[i]) (R07.5.5) |
for x in w.rev | the same loop, hi - 1 down to lo (R07.5.6) |
w.keys, w.len | lo..hi, hi - lo (R07.5.7) |
List(w) | the one allocation: a fresh 0-based copy (R07.5.8) |
- Lending: the rules of
mut a[i], over a range. Any number of read views coexist with reads. Amutview excludes every other access to what it covers; twomutviews not provably disjoint are a compile error (E0601). Halves at one cut (mut a[..c]andmut a[c..], orhalve's two) are provably disjoint. A length change (push,pop,clear) while any view or place is alive is a compile error. (R07.5.9) - Lifetime: second-class, no annotations. A value is lent if any part
of it is (a field, a capture, a generator argument), and a lent value
lives until its last use in the block that made it. It passes into fns
(arguments are always lent) and comes back only from a fn declared
lends, whose result borrows every non-plain parameter unless narrowed:fn window(xs: [V]Int, r: Range<V>) -> lends [V]Int = xs[r],fn pick(a: [V]Int, b: [V]Int) -> lends(a) [V]Int. It never goes in avar, field, container, global or escaping closure. Keeping one isList(w). (R07.5.10) - Parameters. A read-only
xs: [V]Ttakes an array or anyIndexedoverV(amutone, anyIndexedMut); it is a template parameter, so each call site gets its own fused loop.List<T>andStrparameters take only that container (chapter 4b, "User helpers"). (R07.5.11) - Walk-only views.
filter,take_whileand generators areSeqonly: theifor the generator body is inlined into thefor. (R07.5.12)
Generators
fn divisors(n: Int) -> yields Int:
for d in 1..=n.isqrt():
if n % d == 0:
yield d
if d * d != n: yield n / d
for d in divisors(n):
if d > lim: break // break, continue, return, break 'outer, loop else- Push, not pull. The generator runs and the
forbody runs at eachyield, so a non-recursive generator inlines to a plain loop. Recursive generators (DFS, subset enumeration) work the same way, includingbreakandreturnout of the body (§126). (R07.6.1) - A generator value is a closure you walk instead of call.
let g = divisors(n)stores the fn and its arguments and runs nothing; each walk runs the body from the top, with fresh locals and the arguments as they are now. It is owned or lent by what it captured:divisors(12)is owned,dfs(graph, s)is lent,dfs(mut seen)ismut-lent. Walking amut-lent one twice is legal (the second run sees what the first wrote) and linted. Keep the results withList(g). (R07.6.2) - Steering. The yielded item may carry methods the generator reads after
yieldreturns:for step in dfs(g, s): if bad(step.v): step.prune(). This is ordinary library code; any user generator can do it. (R07.6.3) - No lockstep. Two generators can't be walked in step, because each
wants to own the loop. Materialize one (
List(g)), or zip indexed sequences.ziptakes onlyIndexed. (R07.6.4)
Adapters (each makes a view: O(1), lazy)
| Form | Result | Note |
|---|---|---|
s.map(f) | Indexed if s is, else Seq | f runs on every read (R07.7.1) |
s.filter(p), s.take_while(p), s.skip_while(p) | Seq | (R07.7.2) |
s.take(k), s.drop(k) | an O(1) view on an Indexed; a Seq otherwise | consuming a view from the front is w = w.drop(1) (R07.7.3) |
chain(a, b) | Seq | (R07.7.4) |
s.adjacent | Seq<(T, T)>, adjacent pairs | @get, O(1) per step (R07.7.5) |
s.pairs() | Seq<(T, T)>, every pair x before y | O(n²) to walk, so a call (R07.7.6) |
s.with_prev | Seq<(?T, T)>, starting (None, first) | path walks that treat the first step apart (R07.7.7) |
s.cyclic_pairs | Seq<(T, T)>, plus (last, first) | polygons, rings (R07.7.8) |
a.windows(k), a.chunks(k) | Seq of views of a | each view keeps a's indices (R07.7.9) |
a.runs(by: k) | Seq of views: maximal equal-key runs | .keys of each is its range (R07.7.10) |
s.step(k) | every k-th element | ranges and indexed (R07.7.11) |
Parentheses mean work. Only O(1) members read without (): @get
properties such as .len, and views and generators, which cost O(1) to
make and are paid for as you walk them (.rev, .items, .adjacent, .keys,
g.edges, t.tour). Anything that computes or allocates up front is a
call, however few arguments it takes: g.transpose(), t.centroid(),
a.sorted(), .collect(). The spec check rejects an @get whose documented
cost isn't O(1) to make.
Making containers
[f(x) for x in s if p(x)] // List<U>; reserves exactly when there's no filter
[V] v => f(v) // [V]U, filled by f
s.filter(p).map(f).collect() // end of a chain: the type the context expects, else List
List(s) Set(s) Str(s) // conversions of anything that isn't a chain: List(0..n).collect() and the constructors are one operation, O(n) and allocating;
the postfix form is for chains, the prefix form for single values.
Lazy chains redo their work on every consumption. A map calls f on
every read; a filter calls p on every walk. Lint flags a lazy chain
walked twice, or built outside a loop and consumed inside it, and a lazy
map/filter whose closure mutates anything (rng.int(..), count += 1),
suggesting .collect() or a comprehension. Walking a mut-lent value twice
(let a = dfs(mut seen), then two walks of a) gets the sharper message,
since the second walk reruns against what the first wrote.
Folds
| Form | Result | Cost |
|---|---|---|
s.sum(), s.prod() | T; empty is the identity | O(n) (R07.9.1) |
s.fold(op) | T when op has an identity (+, max on a bounded type, gcd), else ?T | O(n) (R07.9.2) |
s.min(), s.max(), s.min(by: k) | ?T, None when empty; first on ties | O(n) (R07.9.3) |
s.count(p), s.any(p), s.all(p) | Int, Bool | O(n) (R07.9.4) |
s.find(p), s.rfind(p) | ?T, linear scan (binary search is r.first_true) | O(n) (R07.9.5) |
Position queries are folds over a.keys, because the keys are a range of
positions. argmin/argmax are kept as the named form of the first
line below (first on ties); there are no first_at or order twins:
a.keys.min(by: i => a[i])! // argmin, first on ties
a.keys.find(i => a[i] > x) // first position with a[i] > x, ?D
a.keys.sorted(by: i => a[i]) // argsort: List<D>
a[l..r].keys.max(by: i => a[i])! // argmax inside a piece, still a position of aScans are prefix sums over cuts
a.scan(op) gives a Prefix<D, T>: n + 1 exclusive folds indexed by D's
cuts. Walking backwards gives suffix folds, indexed by the same cuts:
let pre = a.scan(+) // pre[c]: fold of everything left of cut c
let suf = a.rev.scan(+) // suf[c]: fold of everything right of cut c
pre[r.r] - pre[r.l] // any range r
pre[v] // a position: the fold through v, same as pre[v.r]
prefix(a).fold(r) // same, as the `Prefix` struct (`+` only)
pre[v.l] + a[v] + suf[v.r] // the whole array, split at position vA Prefix takes both kinds of index and the types keep them apart: a cut
folds what lies left of it, a position folds through itself. The inclusive
query (pref_min[v]) is the common one and needs no .r.
O(n) time and memory. This replaces scan, suffix_scan, excl_fold,
scan_in_place and Prefix(...) construction.
Ordering and grouping
| Form | Meaning | Cost |
|---|---|---|
s.sort(by: k), s.reverse(), s.dedup(), s.fill(x) | in place: needs a var source; works on views | O(n log n), O(n), O(n), O(n) (R07.11.1) |
s.sorted(by: k), s.deduped() | new List | same, allocates (R07.11.2) |
s.group(by: k) | Map<K, List<T>> | O(n) expected (R07.11.3) |
s.tally(by: k) | Counter<K> | O(n) expected (R07.11.4) |
compress(s) | (domain C, comp): values sorted and deduped, as a fresh domain | O(n log n) (R07.11.5) |
Sorts are stable. Descending is a key, not a flag: by: x => desc(x.score).
Every in-place verb that has a result-named twin follows the same pattern
(sort/sorted, dedup/deduped); .rev (view) and reverse() (in
place) are different jobs, not twins.
More vocabulary
| Form | Meaning | Cost |
|---|---|---|
s.drop_while(p) | skip the leading elements where p holds, yield the rest | O(1) per step (R07.12.1) |
s.flat_map(f), s.flatten() | each element to a sequence, all inner elements in order | O(1) per element (R07.12.2) |
iterate(x, step) | x, step(x), step(step(x)), ... until step gives None | O(1) per step (R07.12.3) |
s.is_sorted(by:), s.is_subsequence(t) | the two common checks | O(n) (R07.12.4) |
a.partition_point(ok), a.equal_range(x, by:) | on sorted a: the cut where monotone ok turns true; the range equal to x | O(log n) (R07.12.5) |
a.next_permutation(), a.prev_permutation() | step to the neighbouring arrangement in place; false past the end | amortized O(1) (R07.12.6) |
a.rotate_left(k), a.rotate_right(k); s.rotated_left(k), s.rotated_right(k) | rotate in place; a rotated copy | O(n) (R07.12.7) |
m.get_or_insert(k, v) | m[k], storing v first if absent: ids.get_or_insert(name, ids.len) | O(log n) (R07.12.8) |
Answers to round 2's questions
- In-place vs copy: both, by rule: a verb mutates, its result-named twin allocates.
- Folds on possibly-empty input:
NonEmptyis gone. Identity-backed folds (sum,fold(+)) are plainT;min/maxare?Tand you writea.max()!when you know. scan: n + 1 values indexed by cuts; suffix folds come from.rev.
Open
None. Indexed sequences use .keys and domains V.range; .collect()
keeps its name (decision 186).
What goes away
View<T>, view(), 0-based .at(i) / .try_at(i) on Indexed,
drop_first (now drop), skip, step_by, first_at,
order, chunk_by, run_ranges, excl_fold, suffix_scan,
scan_in_place. Each is a view, a fold over .keys, or .rev.scan.