skip to content

Why does transforming every entry before a routine that picks entries without inspecting them equal transforming after it?

level: seniorimportance: nice to knowfreq 26%

answer

  1. nothing proved, it comes from the declaration
  2. positions survive an entry-wise transformation
  3. same slots chosen on both sides
  4. move the expensive step after the pick
  5. holds for a pure, total transformation

basics

~20 s

Because the routine's choice depends only on positions, and transforming entries one at a time leaves positions alone. It takes the same slots either way, so the two orders give the same list — a theorem read straight off the signature.

solid answer

~40 s

A routine declared to take a list of any entry type and return a list of that type can decide only from the list's structure. An entry-wise transformation preserves that structure exactly: same length, same order, each slot's value replaced in place. So the routine selects the same slots whichever side of it the transformation runs, and the two pipelines produce the same result. This is a **free theorem** — free because nobody proved anything about the body; the declaration alone forces it, which is the content of Reynolds' abstraction theorem. It licenses a real refactor: move the transformation after the pick so you only pay for the entries that survived. It assumes a pure, total transformation and a routine that terminates without effects.

code

pseudocode · 8 lines
pseudocode
// draw(entries: list of T) -> list of T, never inspecting an entry
// transform_each(f, xs) applies f to every entry, keeping order and count

left  = transform_each(f, draw(entries))
right = draw(transform_each(f, entries))

// left == right for every total, effect-free f and every list of entries
// left runs f once per winner; right runs it once per entry

go deeper

for a junior

Take away the shape of the claim: if a routine never looks at what it is moving around, it does not matter whether you change the things before or after it moves them.

for a middle

Explain why positions are the pivot — an entry-wise transformation leaves length and order untouched, so the same slots get chosen on both sides of it.

for a senior

Show the refactor and its limit: move the expensive transformation after the selection, and state clearly that the guarantee covers the values returned, not how many times the transformation ran.

for a principal

Consider what it means for standards: properties derivable from a declaration need no tests and survive every rewrite of the body, which is an argument for declarations narrow enough to derive things from.

## What a free theorem is Most properties of a routine are established by reading its body or by testing it. A **free theorem** is a property you get without doing either: it follows from the declaration, because a body that satisfies that declaration cannot behave in any way that would break it. The general result behind this is **Reynolds' abstraction theorem** — related pairs of arguments produce related pairs of results — but interviewers do not want the theorem stated. They want the consequence, and the consequence is a rewrite you are allowed to make. ## The theorem for a prize draw Take the draw again: a list of entries of any type in, a list of that type out, entries never inspected. Let `transform_each` apply some transformation to every entry, keeping order and count. Then for every such transformation and every list of entries: > transforming all the entries and then drawing gives exactly the list you get by drawing first and transforming the winners. ## Why the argument works The reasoning is short enough to give at a whiteboard: 1. The draw can only decide **which slots** to take — it cannot see what is in them. 2. An entry-wise transformation changes what is in each slot and **nothing else**: same number of entries, same order, no slot added or removed. 3. So the draw is looking at an identical structure in both pipelines and takes the same slots. 4. Taking slot *k* and then transforming its value, or transforming that value and then taking slot *k*, produce the same value. Run through it on three entries where the draw takes the last slot and then the first. Transform first, and the draw takes the transformed last and the transformed first. Draw first, and you transform exactly those two. Same list. ## The conditions, which are the honest part The law is not unconditional, and a candidate who states it as though it were has missed the interesting half: - **The transformation must be a function** — same entry in, same value out, every time. One that consults a clock or a counter produces different values on the two sides. - **The transformation must be total and effect-free.** If it fails or emits an effect, the two pipelines differ in *how many times* it runs: transforming first touches every entry, transforming after touches only the winners. The surviving values may match while the effects do not. - **The routine must terminate and be effect-free.** Both are outside what any signature promises. - **The routine must genuinely be unable to inspect an entry.** A run-time test inside the body voids the theorem immediately. | Pipeline | Transformations run | Result | |---|---|---| | transform every entry, then draw | one per submitted entry | the same winners | | draw, then transform the winners | one per winner | the same winners | The right-hand column is what the theorem guarantees; the middle column is what it does **not**, and it is usually the reason to prefer one order. ## What it buys in practice Two things, both concrete: - **A refactor with no reading required.** If the transformation is expensive — decoding, formatting, enriching — do the cheap selection first and transform the survivors. You do not need to open the draw's body to know this is safe, which is what makes the rewrite cheap on a codebase nobody fully knows. - **A test you do not have to write.** Anything that follows from the declaration cannot be broken by a change to the body that keeps the declaration. Spending a test on it is spending it on something the type system already holds. ## A second theorem from the same declaration The same reasoning gives another property for free: the **length of the result depends only on the length of the input**. Two lists of equal length produce results of equal length, whatever entries they contain. That one is often more useful in review than the commuting law, because it says a draw cannot decide to return more winners for a more interesting field of entries — and if the product wants it to, the declaration has to change first.

  • What quietly breaks the law if the transformation can fail?
    The count of how many times it runs. Transforming before the draw touches every entry, so a failure on an entry nobody would have picked still sinks the call; transforming after touches only the winners. The returned values agree whenever both sides finish — the failure behaviour does not.
  • Name a second property the same declaration gives you for free.
    The result's length depends only on the input's length. Two lists of the same size yield results of the same size regardless of their contents, because the body decides from structure alone. That makes behaviour testable with one representative list per length.
  • How would you use this law in a code review?
    As permission to move an expensive per-entry step across the pick without reading the body. If the declaration says entries are never inspected, reordering the two stages is guaranteed to preserve the result, and the only thing left to weigh is how many times the expensive step now runs.

saying these in an interview costs you the question

  • States the law with no conditions on the transformation
  • Thinks the law needs the body to be read and verified
  • Says both orders also run the transformation equally often
  • Believes the transformation must preserve the entry type
  • Claims a test is needed to confirm the rewrite is safe