Parsing every row of an import batch into a fallible result: what does a single traversal do that mapping then inverting does not?
answer
- two spellings, one value
- traverse is map then invert
- one pass, no intermediate collection
- step calls stop at the failing row
- matters when the step acts
basics
~20 sA single traversal applies the step and combines as it goes, building no intermediate collection of wrapped results and calling the step no further than the first failure. Mapping first runs the step on every row.
solid answer
~50 sThe two spellings return the same value for a pure step - traversing with a step *is* mapping with it and then inverting, which is where the operation gets its definition. What differs is how the work is done. Mapping first walks the batch once and produces `n` wrapped results, all of which sit in memory before the inversion begins; the inversion then walks them and short-circuits at the first failure - too late, because the step has already been applied to every row. A one-pass traversal interleaves the two: it applies the step to a row, folds the result in, and returns as soon as a row fails. When the step is pure and cheap the difference is invisible. When the step performs an effect as it is called - a lookup, a write, a rate-limited call - the difference is `k` effects instead of `n`.
code
pseudocode · 12 lines// two steps: apply to every row, then invert
wrapped = map(rows, step) // step called once per row, all n
result = invert(wrapped) // stops at the first failure it finds
// one pass: apply and combine together
function traverse(rows, step):
out = empty list
for each row in rows:
r = step(row) // not called past the failing row
if r is failure: return r
out.append(value of r)
return success(out)go deeper
Know that applying a fallible step to every row and getting one wrapped collection has a name, and that it is the same as mapping and then inverting.
Explain the identity behind the two spellings and then name what differs: one pass instead of two, no intermediate collection, and no step calls past the failing row.
Argue it from a real batch path: an acting step spends n - k effects it can never take back, and those effects are not undone by the failure the caller finally sees.
Set the expectation for batch code in general - where an acting step may be applied, and whether shared tooling exposes the fused form only.
## Two spellings of one result There are two ways to turn a batch of rows and a fallible per-row step into one fallible collection: - **Map, then invert.** Apply the step to every row to get a collection of wrapped results, then invert that collection into one wrapped collection. - **Traverse.** Apply the step and combine the result into the accumulator in the same pass. The second is *defined* as the first: traversing with a step means mapping with it and then inverting. That identity is why the returned value is the same for a pure step, and it is the first thing to say when asked. ## Where the two stop being the same The difference is in the work performed, not the value returned: - **Step invocations.** With a fail-fast context and a batch that fails at row `k` of `n`, an eager map calls the step `n` times; the traversal calls it `k` times. The inversion in the two-step spelling can short-circuit, but only over results that already exist. - **Intermediate memory.** The two-step spelling materialises `n` wrapped results before the inversion begins, and then the collection of unwrapped values as well. - **Effects.** When the step performs its effect as it is called, the two-step spelling performs `n` of them even though the batch is already doomed at row `k`. If the step is instead a description of an action to be run later, nothing has happened yet in either spelling and this difference disappears. - **Time to first signal.** The traversal can report the failing row as soon as it meets it; the two-step spelling reports it only after the whole batch has been processed. ## Side by side | | map, then invert | one-pass traversal | |---|---|---| | passes over the batch | two | one | | step calls when row `k` of `n` fails, fail-fast | `n` | `k` | | peak intermediate structures | `n` wrapped results, then `n` values | `k` values | | effects past the failing row, acting step | performed | not performed | | value returned, pure step | identical | identical | ## When the difference does not matter - **The step is pure and cheap.** Parsing a number from a string a few thousand extra times is not a cost anyone will measure. - **The batch is small and already in memory.** The intermediate collection is then a rounding error. - **The traversal collects every failure instead of stopping.** This is the case people state backwards: a collecting traversal deliberately runs the step on **every** row, so it makes the same `n` calls either way and the short-circuit advantage simply does not exist there. The memory and pass-count differences remain. - **The failure is expected at the very end or not at all.** If most batches are clean, `k` is `n` anyway. ## When it matters a great deal 1. **The step touches something outside the process** - a per-row lookup, a write, a quota-limited call. Then the two-step spelling spends `n - k` of them after the batch is already lost, and any of them that mutate state are not undone by the failure the caller eventually receives. 2. **`n` is large.** Millions of wrapped results held only so the next pass can discard them is memory spent for nothing. 3. **The step is expensive per row** - decryption, a costly computation, a slow parse. 4. **Failures are common and early.** A batch that usually fails in its first hundred rows makes the gap between `k` and `n` the whole story. ## The review question to ask When you see mapping followed by an inversion in a batch path, ask three things in order: does the step do anything besides compute a value; how large can the batch get; and how early is a failure likely? If the answers are "it writes", "millions" and "often", the two-step spelling is not a style preference, it is `n - k` avoidable effects and a collection you never needed. If the answers are "it is pure", "a few hundred" and "rarely", the two spellings are equivalent and you should pick whichever reads better to the next person.
- If both spellings return the same value, why is the one-pass form the default in most libraries?Because it is the strictly better default: identical result, one pass, no intermediate collection, and no step calls past a failure. The two-step form is kept because it explains what the traversal means, and because it is occasionally clearer when the mapped collection is wanted for its own sake.
- Does the step-call advantage survive when the traversal collects every failure rather than stopping?No. A collecting traversal runs the step on every row by design, so both spellings make the same number of calls. What survives is the single pass and the absence of an intermediate collection of wrapped results.
- The step returns a described action to run later rather than performing work when called; what changes?The effect difference disappears, because neither spelling has performed anything yet - both have only built descriptions. The pass count and intermediate memory still differ, and the built description itself may be far larger in the two-step form.
saying these in an interview costs you the question
- Says the two spellings return different values for a pure step
- Thinks the eager map short-circuits at the first failing row
- Claims the difference is only intermediate memory
- Assumes the traversal reorders rows to fail faster
- Says the short-circuit advantage also applies when collecting failures