What do you learn about a fold by rewriting a mapping stage and a filtering stage as folds?

## The two rewrites Take the day's transactions. A stage that converts each one to its net amount, and a stage that keeps only the card payments, both become folds over an empty collection: ```pseudocode // mapping stage as a fold netAmounts = fold(transactions, [], function(acc, t) { return append(acc, netOf(t)) }) // filtering stage as a fold cardOnly = fold(transactions, [], function(acc, t) { return isCard(t) ? append(acc, t) : acc }) ``` Neither rewrite needed a new construct. The seed chose the accumulator's type, and the step decided what - if anything - each element contributed to it. ## What the rewrite actually demonstrates - **The accumulator's type is free.** This is the headline. A fold is not "the thing that produces a number"; it produces whatever the seed's type is, and a collection is an ordinary choice of seed type. - **The shape-preserving stages are constrained folds.** A mapping stage is the special case where every element contributes exactly one entry and the converted value ignores the accumulation so far. A filtering stage is the case where every element contributes one entry or none, unchanged. Both give up the freedom to look at what has accumulated. - **Fold is the general consumer of the structure.** It is the one operation in this vocabulary that can change the result's shape, which is why folding is sometimes given the general name **catamorphism**: the operation that collapses a structure according to how the structure is built. - **Going the other way does not work.** A mapping stage and a filtering stage each hand back a structure of the same kind and never expose a running accumulation, so there is no arrangement of them that turns a thousand transactions into one totals record. Generality runs one way here. | Operation | Result shape | Entries out, per element in | Can the step see the accumulation? | |---|---|---|---| | Mapping stage | same kind of structure | exactly one | no | | Filtering stage | same kind of structure | one or none, unchanged | no | | Fold | whatever the seed's type is | not applicable - one result overall | yes | ## Why this is a lesson and not a licence Every interview answer here has a second half, and leaving it out is what makes a candidate sound clever rather than employable. **Do not rewrite readable stages as folds.** A named per-element stage announces its contract in its name: same count out as in, or a subset in the original order. A fold announces nothing except that an accumulator exists, and the reader must decode the step to find out whether the count changed, whether order survived, and what type comes back. The working rule is to reach for the **most specific operation that does the job**, and to reach for the fold when the result genuinely changes shape - one record, one total, one largest sale, one grouping - or when the step needs to look at what has accumulated so far, which is the one thing the shape-preserving stages structurally cannot do. ## The cost trap in the rewrite The rewrites above append to the accumulator once per element, and appending is where the hidden cost sits. If each append copies the collection accumulated so far, an n-element fold does work proportional to n squared, and the rewrite that was supposed to be equivalent is quadratic where the original was linear. The usual fixes are to accumulate into a structure whose extension shares its existing contents rather than copying them, or to accumulate into a mutable local builder that never escapes the fold and to hand back a finished value at the end. State what `n` is when you discuss this: it is the number of elements, and the copying cost is per element, which is where the second factor comes from. ## A related sharp edge If the accumulator is a collection and the step prepends rather than appends, the result comes out reversed. That is a real defect in a reconciliation report where the order is the day's sequence, and it is a favourite follow-up: the interviewer wants to see that you noticed the ordering obligation the original stage was quietly meeting for you. ## What an interviewer is checking This is a differentiator question rather than a screening one. It separates a candidate who has memorised three named operations from one who sees the vocabulary's structure - and the good answer ends by declining to use the general operation where a specific one reads better.