Why can the stages of a composed text-normalisation pipeline be regrouped freely but never swapped with each other?
answer
- brackets are free, order is not
- associative but not commutative
- every stage still sees the same input
- a swap changes the intermediate value
- a commuting pair is about that pair
basics
~20 sComposition is associative but not commutative. Regrouping only changes which adjacent stages get bracketed together, so every stage still receives the same input; swapping two changes what the later one is handed, and therefore the result.
solid answer
~50 sAssociativity says that bracketing does not matter: for stages `f`, `g`, `h`, composing `f` with the pair `(g, h)` gives the same function as composing the pair `(f, g)` with `h`. Commutativity would say that order does not matter, and composition does not have it. The reason is that brackets only decide which adjacent pairs you give a name to - the sequence each value passes through is untouched - whereas a swap changes the intermediate value the next stage sees. Take trimming, collapsing runs of whitespace, and truncating to ten characters: bracket them any way you like and the answer is the same, but truncate before collapsing and the truncation spends its budget on padding. Particular pairs may happen to commute, such as case folding and accent stripping; that is a fact about those two stages, not about composition.
code
pseudocode · 13 lines// compose(f, g) means the stage x -> f(g(x))
input = " hello world " // 2 spaces, 4 between the words, 2 trailing
// regrouping: bracket either adjacent pair, same function
a = compose(truncate10, compose(collapseSpaces, trim))
b = compose(compose(truncate10, collapseSpaces), trim)
// trim -> "hello world", collapse -> "hello world", truncate10 -> "hello worl"
// a(input) == b(input) == "hello worl"
// reordering: swap the last two stages, different function
c = compose(collapseSpaces, compose(truncate10, trim))
// trim -> "hello world", truncate10 -> "hello w", collapse -> "hello w"
// c(input) == "hello w"go deeper
Learn the one-line version: brackets are free, order is not. Be ready to give one concrete pair whose order changes the answer, such as truncating before versus after collapsing runs of whitespace.
Explain why both bracketings unfold to the same nested application, and why a swap hands the later stage a different intermediate value. A worked trace on one input is the answer interviewers want.
Show the consequence in a live system: a reordered pipeline that silently changed what was written to an index, and the fact that regrouping a chain is a safe refactor while resequencing it is a behaviour change needing a reindex.
Decide what the team may treat as free. Making regrouping an explicitly safe refactor - and any order change a reviewed behaviour change with a named counterexample or a pinning test - is a cheap standard that prevents a whole class of silent index corruption.
## Two laws that sound alike Composition of stages obeys one algebraic law and not another, and conflating them is the mistake this question is built to catch. - **Associativity** (holds): `compose(compose(f, g), h)` and `compose(f, compose(g, h))` are the same function - they agree on every input. Brackets are free. - **Commutativity** (does not hold in general): `compose(f, g)` and `compose(g, f)` are generally *different* functions. Order is not free. Throughout, `compose(f, g)` denotes the stage `x -> f(g(x))`. The practical translation is the one worth memorising: **you may regroup a pipeline, you may never reorder it.** ## Why regrouping cannot change anything Think of the pipeline as a value travelling through a sequence of stages. Bracketing is a statement about *naming*, not about *routing*. If you take the trim stage and the collapse stage and give the pair a name - say `tidyWhitespace` - the value still leaves trim and arrives at collapse exactly as before; you have only chosen to talk about the two of them as a unit. Nothing about the adjacency changed, and the adjacency is all that determines the output. That is why associativity is not a lucky accident of these particular stages. It falls out of what function application means: both bracketings unfold to `f(g(h(x)))`, character for character. No property of `f`, `g` or `h` is needed. ## Why reordering changes the value A swap changes the input of the later stage. `f(g(x))` feeds `f` the output of `g`; `g(f(x))` feeds `g` the output of `f`. Unless those two intermediate values coincide for every input, the two pipelines are different functions. Trace one input through a three-stage normaliser - trim, collapse runs of whitespace to one space, truncate to ten characters - on the text `" hello world "` (two leading spaces, four between the words, two trailing): | Pipeline | Intermediate values | Result | |---|---|---| | trim, then collapse, then truncate | `"hello world"` then `"hello world"` | `"hello worl"` | | trim, then collapse and truncate bracketed together | identical intermediates | `"hello worl"` | | trim, then **truncate**, then **collapse** | `"hello world"` then `"hello w"` | `"hello w"` | The first two rows differ only in bracketing and agree. The third differs in order and loses most of the second word, because truncation spent six of its ten characters on padding that had not been collapsed yet. ## What the law licenses in practice Associativity is what makes the following refactorings safe without re-testing the pipeline's outputs: - Give a sub-chain a name and use it on its own elsewhere. - Move the boundary between two halves of a long chain to wherever it reads best. - Precompute or cache the result of a prefix of the chain, since the prefix is itself a stage. - Build the chain by combining stages pairwise in whatever grouping the assembly code finds convenient. And what it does not license: - Sorting stages by cost, so the cheap ones run first. - Letting a configuration file list stages in any order it likes. - Assuming that because two stages commuted on your sample text, they commute on all text. ## The pair that happens to commute Some pairs genuinely do commute. Case folding and accent stripping usually give the same answer in either order, because they touch disjoint aspects of a character. When that is true it licenses swapping *that adjacent pair* - and nothing more. It is a theorem about the two stages, established by reasoning about what each one does, not a property of composition. Two traps follow. First, it is easy to verify on one alphabet and be wrong on another, where folding case changes which accent is present. Second, a pair that commutes today may stop commuting when one of the two stages grows a new rule, and nothing in the type of a stage records the promise. Treat a relied-upon commuting pair as a documented assumption with a test, not as a fact about pipelines. ## The review checklist 1. Does the change alter the **sequence** of stages, or only the **brackets**? Brackets are free; sequence is a behaviour change. 2. If the sequence changed, name the input on which the two orders disagree. If you cannot produce one, you have not yet shown they commute - you have only failed to find the counterexample. 3. If you are relying on a commuting pair, write the test that pins it, because the next edit to either stage can quietly break it.
- Two stages agree in either order on every input you tried. What have you actually established?That you found no counterexample - which is weaker than commuting. Commuting has to be argued from what the two stages do, for example that one only changes case and the other only strips accents. Even then it is a promise about that pair alone, it does not generalise to other stages, and it can be broken by a later edit to either one.
- Does associativity still hold when the stages change type along the way, say text to tokens to a normalised list?Yes. Bracketing never touches adjacency, so as long as each stage's output type matches the next stage's input type, both bracketings type-check and compute the same value. What you lose with mixed types is the freedom to compose arbitrary pairs - only the neighbours whose types line up can be bracketed together.
- A team wants to reorder stages so the cheapest one runs first. Is that ever acceptable?Only where the affected pair has been shown to commute, and then only for that pair. Cost is not a licence: associativity says nothing about order. The usual safe version of the wish is different - keep the order and make an early stage cheaper, or bracket a prefix and cache its result, both of which are regroupings rather than reorderings.
Putting on socks and then shoes: you are free to think of it as one step called 'footwear' or as two, but you cannot put the shoes on first.
saying these in an interview costs you the question
- Says composition commutes because every stage is text-to-text
- Claims associativity means the stages may run in any order
- Assumes two stages that agree on sample input commute on all input
- Thinks naming a sub-chain as one stage can change the output
- Argues order only matters when a stage has side effects