Lazy iterators over Vec[T] / []T

Audience: Nova users. Spec: D260 (lazy iterator model), D277 (by-value BoxIter + zero-cost vec_iter_zc), D239 ([]T ≡ Vec[T]). Internals: vec-internals.md. Plan 153.2.

A lazy iterator processes a vector one element at a time, on demand, with no intermediate allocations. Building a pipeline does no work; only a terminator pulls elements through it, and it pulls only as many as it needs.

import std.collections.vec_lazy

ro v = Vec[int].of(1, 2, 3, 4, 5, 6)
ro got = v.lazy().map(|x| x * 10).filter(|x| x > 25).collect()
assert(got == [30, 40, 50, 60])

Getting started

The lazy layer is an opt-in module — import it explicitly:

import std.collections.vec_lazy

(It is not in the prelude: lazy adapters take closures, and a prelude-global closure-carrying method would leak its generics/params into every unit — see vec-internals.md. The eager collections.vec_seq combinators are confined the same way.)

Every pipeline starts with v.lazy(), which turns a Vec[T] (or any []T, since they are the same type — D239) into a BoxIter[T]:

v.lazy()  →  BoxIter[T]   →  .map(..) .filter(..) ...   →  terminator
  ^entry        cursor          ^adapters (lazy)             ^drives the chain

Lazy vs eager — why it matters

Lazy is the canonical, allocation-free path (Q-iterator-laziness). The eager vec_seq combinators are retained as a transitional surface; reach for lazy() when you chain more than one step or want short-circuiting.

Laziness, demonstrated

Nothing runs until a terminator drives the chain, and only the pulled elements are touched:

ro v = Vec[int].of(1, 2, 3, 4, 5)

// No terminator → no work. `map` never runs.
ro _pipeline = v.lazy().map(|x| x * 2).filter(|x| x > 0)

// `take(3)` pulls exactly 3 source elements — `map` runs 3 times, not 5.
ro first3 = v.lazy().map(|x| x * 10).take(3).collect()   // [10, 20, 30]

// `find` short-circuits at the first match.
ro hit = v.lazy().map(|x| x).find(|x| x == 3)            // Some(3), map ran 3×

API — Phase A

Entry

Adapters (lazy — return a new BoxIter, no allocation)

Slice-view iterators (lazy []T-view producers — Plan 153.4)

Instance methods on Vec[T] (not on BoxIter) that split the vector into a lazy iterator of zero-copy []T views (Vec[T] headers with cap == len, sharing the parent buffer like v[a..b]). No outer Vec[Vec[T]] is allocated up front — each step pull builds one sub-range view on demand (Rust slice::chunks / windows). Each requires n > 0 (a zero/negative size panics, no clamp). Drive them with any terminator: v.chunks(n).collect() materialises the [][]T only on demand, v.windows(n).map(|w| …) / .fold / .count never allocate the outer Vec at all.

ro v = Vec[int].of(1, 2, 3, 4, 5)
assert(v.chunks(2).collect().len() == 3)             // [1,2] [3,4] [5]
assert(v.chunks_exact(2).collect().len() == 2)       // [1,2] [3,4] (drops [5])
assert(v.windows(2).collect().len() == 4)            // [1,2] [2,3] [3,4] [4,5]
// lazy — no Vec[Vec[int]] ever allocated:
ro pair_sums = v.windows(2).map(|w| w[0] + w[1]).collect()
assert(pair_sums == [3, 5, 7, 9])

Terminators (drive the chain / short-circuit)

sum(zero T) takes the additive identity (0 / 0.0) explicitly instead of relying on a numeric protocol — it makes the element type and the empty-iterator result unambiguous.

Recipes

import std.collections.vec_lazy

// Transform then collect
ro doubled = v.lazy().map(|x| x * 2).collect()

// Filter then sum
ro total = v.lazy().filter(|x| x % 2 == 0).sum(0)

// Sum of squares of the odd elements
ro s = v.lazy().map(|x| x * x).filter(|x| x % 2 == 1).fold(0, |acc, x| acc + x)

// Window the middle: drop 2, keep 3
ro mid = v.lazy().skip(2).take(3).collect()

// filter_map: keep + transform in one pass
ro tripled3 = v.lazy()
    .filter_map(|x| if x % 3 == 0 { Some(x * 10) } else { None })
    .collect()

// enumerate: project index + value in the SAME stage (collapse the tuple with map)
ro projected = v.lazy().enumerate().map(|p| p.0 * 100 + p.1).collect()

// Short-circuiting search — stops at the first match
ro found = v.lazy().find(|x| x > 100)

// Bounded scan — only the first 3 are ever touched
ro early = v.lazy().map(|x| x + 1).take(3).any(|x| x == 3)

FromIterator / collect-target (Plan 153.6, D264)

Materialise a pipeline (or any iterator source) into a chosen collection.

import std.collections.vec_lazy
import std.collections.set.{Set}
import std.collections.hashmap.{HashMap}

// Default target — Vec
ro v = src.lazy().map(|x| x * 2).collect()

// Set target — dedup (Rust `iter.collect::<HashSet<_>>()`)
ro s = src.lazy().filter(|x| x > 0).collect_set()

// HashMap target — collect pairs, then `from`
ro m = HashMap[int, int].from(src.lazy().map(|x| (x, x * x)).collect())

// Set target (alternative) — collect a Vec, then `from_iter`
ro s2 = Set[int].from_iter(src.lazy().collect())

// Build a Vec from ANY Iter source directly (no lazy stage) — `@extend`
ro from_range = Vec[int].new().extend(0..5)        // [0, 1, 2, 3, 4]
ro from_vec   = Vec[int].new().extend(other_vec)   // copy

Nova types iterators structurally (D58): any mut @next() -> Option[T] is iterable, so FromIterator is a set of constructors/terminators rather than one enforced single-method protocol — @collect/@collect_set (terminators), from/from_iter (constructors from a collected Vec), @extend (build from a source). Gated (compiler gaps, not simplifications): a static generic Vec[T].from_iter[S Iter[T]] constructor ([M-153.6-collect-static-generic] — use Vec[T].new().extend(src)) and a tuple-element @collect_map() terminator ([M-153.6-collect-map-tuple-receiver] — use HashMap.from(pairs.collect())).

Known limits (Phase A)

• enumerate then a tuple-preserving adapter. enumerate().map(|p| ...) (the map consumes the (int, T) tuple in the same stage) is supported. Chaining a tuple-PRESERVING adapter directly after enumerate — enumerate().filter(..) / .take(n) / .skip(n), where the element stays the tuple — is gated on a residual closure-typing gap ([M-153.2-tuple-elem-adapter]); collapse the tuple with map first.
• Phase B adapters not yet present (roadmap, not a simplification): zip/unzip/chain/flat_map/flatten/scan/inspect/step_by/ take_while/skip_while/peekable/min_by[_key]/max_by[_key]/partition/ chunk_by/into_iter, plus mutable iteration (for mut x / mut @iter()). (FromIterator/collect-target is done — see D264.)
• Cost. BoxIter[T] is now a value record (D277 Stage 1), so the wrapper record itself costs zero heap allocations — a v.lazy().map().filter().collect() chain went from 5 BoxIter heap boxes to 0, passed by value on the stack. What remains boxed in this model is the per-adapter step closure (a heap thunk + a box of the captured source, plus a step() pointer call per element). For an allocation-free and indirection-free chain, use the zero-cost generic-over-source sibling — see below.

Zero-cost sibling — collections.vec_iter_zc

vec_lazy/BoxIter is the closure-fluent surface: one erased cursor type, uniform BoxIter[T] at every stage, at the cost of a boxed step per adapter. For hot paths there is an allocation-free, indirection-free sibling module:

import std.collections.vec_iter_zc

ro v = Vec[int].of(1, 2, 3, 4, 5, 6)
ro got = v.ziter().zmap(|x| x * 10).zfilter(|x| x > 25).zcollect()
assert(got == [30, 40, 50, 60])

Each adapter is its own generic-over-source value record (MapIter[I,T,U] / FilterIter[I,T] / FilterMapIter[I,T,U]) that holds the upstream iterator inline as a field src I — not a boxed step closure. @next() calls (@src).next() by a static, monomorphized dispatch, so a chain v.ziter().zmap(f).zfilter(p) monomorphizes to a single nested concrete type FilterIter[MapIter[VecIter[int], int, int], int], and every .next() inlines down to the base VecIter.next() — no per-element function-pointer call.

The adapter-on-adapter methods write their return type with Self as a nested generic type-argument — e.g. MapIter[I,T,U] @zmap(...) -> MapIter[Self,U,V] (where Self ≡ MapIter[I,T,U], the receiver mono), and likewise -> FilterIter[Self,U] / -> FilterMapIter[Self,U,V]. This drops the repeated receiver-type in the re-nesting position; semantics are identical to spelling the receiver type in full. Compiler support for Self as a nested generic type-arg (return and param) on a value-generic mono landed 2026-06-15 — see D66 → AMEND «Self как вложенный generic type-arg». (Chain-ENTRY VecIter[T] @zmap -> MapIter[Self,T,U] is not yet covered — the single-param VecIter[T] source stays explicit; [M-138.2-self-in-param].)

For the canonical map().filter().collect() chain this removes 6 adapter allocations and 9 source boxes. As of D277 Stage 3, a closure with no captures (the common |x| x * 3 form) costs 0 heap too — it is emitted as a file-scope static singleton instead of a per-call-site env-box + closure-box (measured: closure allocs 4 → 0 for the .zmap().zfilter().zcollect() chain, 6 → 0 with a .zfold()). The only heap left for an all-capture-free chain is the VecIter source cursor; a capturing closure still allocates its env per instance (irreducible without closures-as-mono-types — [M-153.2-closure-as-mono-type]), and the call itself is still a fn-ptr indirection ([M-153.2-Z-closure-devirt]).

Allocation summary (canonical chain over a Vec[int], measured in generated C):

The two coexist behind separate explicit imports — vec_iter_zc is not a replacement. Reach for it on hot paths; vec_lazy stays the ergonomic single-cursor default. Entry is v.ziter(); adapters zmap/zfilter/ zfilter_map; terminators zcollect/zcollect_into/zfold/zcount/zsum/ zfor_each/zany/zall/zfind. take/skip/enumerate (stateful / tuple-element) remain on boxed vec_lazy for now.

zcollect_into(out) is the allocation-free sink (D277 Stage 4): it drains the chain by appending into a caller-supplied reusable Vec[T] instead of allocating a fresh result. Its monomorphized body is 0 nova_alloc. Clear the buffer first to use it as a fresh sink (out.clear() keeps the backing store, so a reused out amortizes to zero allocations):

mut out = Vec[int].new()
for batch in batches {
    out.clear()                                       // len=0, buffer kept
    batch.ziter().zmap(|x| x * 2).zfilter(|x| x > 0).zcollect_into(out)
    consume(out)                                      // reuse `out` next iteration
}

See also

• vec-internals.md — module layout, the boxed-fluent shape, the zero-cost generic-over-source sibling, Compare/Equal.
• D260 — boxed-fluent decision record.
• D264 — Hash + FromIterator / collect-target.
• D277 — by-value BoxIter monomorphization + the zero-cost vec_iter_zc sibling.
• D58: ../spec/decisions/03-syntax.md — Iter/Next structural iteration.
• Q-iterator-laziness — why lazy is the canon.