Status: Accepted
Date: October 12, 2026 (#595)
Answers: whether xs.map(f).map(g) builds a list between its two steps,
and what the compiler may change in a chain so that the chain a program writes
runs as the loop a person tunes by hand, with every check the language promises
Related:
ADR-293 D20 (a sequence’s pipeline is one loop, none of it allocating);
ADR-306 (a check a proof shows unneeded is not emitted, and the program means the same either way);
ADR-327 D5, D10 (what a task allocates counts against its budget);
Part I 4.5, 5.3 (a list’s map is a list), Part III 13.5 (touches), Part III A.2 (an overflow stops the task and names its line)
May a chain over a list run its steps element by element, and what may it change in what a program sees?
A list’s map hands back a list (Part I 5.3), so xs.map(f).map(g) walks the
list twice and builds a list nobody names between the walks. Under ADR-327
that list takes room in the task’s block. A chain over a sequence,
xs.iter().map(f).filter(g), is one loop already (ADR-293 D20), but every
overflow check in it is a branch per element, and a loop with a branch per
element is not vectorized; a filter with two conditions is two branches per
element. A program written as a plain chain - the way a model writes it - is
the one that has to be fast.
| Language / tool | Its answer | What it costs there | Source |
|---|---|---|---|
| Rust iterators, Java streams | lazy: nothing is built between steps; element by element, in a fixed order | an eager result is a written collect |
from memory, not checked |
Kotlin List.map, Swift Array.map |
a list per step; asSequence() / .lazy to fuse |
the fused form is a second spelling | from memory, not checked |
| Haskell (GHC) | fused by rewrite rules (foldr/build) |
invisible, because nothing has effects | from memory, not checked |
| Mojo | vectorized where the program writes it: SIMD[DType, n], vectorize |
the fast code is a second program; integer overflow is not checked | from memory, not checked |
| C and C++ compilers | loop fusion and vectorization only where the effects allow | a check per element (-ftrapv) stops vectorization |
from memory, not checked |
What does not transfer: Haskell’s purity. Nikaia knows per lambda whether it
touches anything (Part III 13.5) and whether it changes a name outside it
(NK2107), so the rule below can ask what Haskell takes for granted.
| Option | Why it lost, or won |
|---|---|
| A Keep every step’s list, as today | passes and memory the program never asked for |
B A list’s map becomes lazy everywhere, as Rust’s |
changes the order of effects in programs that print or read in a lambda, and let ids = users.map … stops being a list |
| C Fuse only where nothing at all could differ, panics included | nearly every lambda with arithmetic can overflow, so it would almost never apply |
| D Explicit vector types, as Mojo | the fast program is a second program; the plain chain stays slow |
| E Element by element where the lambdas touch nothing; which panic stops such a chain, and where an overflow does, not fixed | chosen |
| D1 the special case pays | D2 the compiler works | D3 no cost for the common case | D4 consistent | If it is wrong | |
|---|---|---|---|---|---|
| A | yes | yes | no: a pass and a list per step | yes | - |
| B | no: programs with effects change | yes | yes | no: map is a list in 5.3 |
silent reordering of output |
| E | yes: a chain that panics twice may report the other one | yes | yes | yes: a chain over a sequence already runs element by element | a panic message names the other step |
map whose result goes straight into another step runs element by element with it.xs.map(f).map(g), xs.map(f).iter()…, for x in xs.map(f) and
xs.map(f).len() build no list between the steps, where every lambda of the
chain touches nothing (Part III 13.5) and changes no name outside it - what a
par_iter lambda is asked, except that it may pause. A result that is named,
or that a step needs whole (sort, an index), is a list as it is today. A
chain with a lambda that touches something runs as written, step after step.
The chain computes the same result in any order. Where more than one of its steps would panic, which one stops the task is not fixed. It stops only for a reason one of its steps has on a value the chain computes as written. This holds for a chain over a sequence too (ADR-293 D20).
The compiler may carry an overflow to the end of the chain, or of a run of its elements, and stop there, naming the line of the operation that overflowed, as A.2 does. Nothing the chain computed is seen in between: its result does not exist yet. A value that overflowed reaches no index, division or condition before the stop, so D2’s last sentence holds. This is what lets a chain keep its overflow checks and still be vectorized.
Where a filter’s later condition cannot panic, both conditions may be read and
joined with one branch (& for &&). A filter may write every element and
move its end by the condition, with no branch at all. Either changes nothing a
program means.
D1 does less work than the steps it replaces, and is built without a
measurement. D3 and D4 can be slower: an overflowing_ operation and an or
where nothing is vectorized, a write per element where the condition was
predictable, a second condition read that a short circuit skipped. Each is
emitted for the shapes of chain where a count (instructions and mispredicted
branches, callgrind) shows it is not slower than today’s code; elsewhere today’s
code stays. D1 is measured for one shape only: a fused loop whose one step would
be vectorized on its own and whose other would not.
xs.map(f).map(g) is one pass, and takes no room in the task’s block between
its steps.filter and the other adapters become a list’s methods too (today
xs.iter().filter).par_iter chain (Part II 12.6).vectorize for code that is not a chain.spawn is concurrency the program wrote and stays so;
what a value costs when it moves between tasks is ADR-327 D9.