In a fold that collapses a day of till transactions into one totals record, what do the seed and the combining step each contribute?
answer
- many values in, one value out
- three inputs, not two
- a starting accumulator, not a first element
- empty structure returns the seed
- step shape: (accumulator, element) -> accumulator
basics
~20 sThe seed is the accumulator's starting value and the result returned for an empty day. The combining step takes the accumulator so far plus one transaction and returns the next accumulator. A fold threads that accumulator through every element.
solid answer
~40 sA fold needs three things: the sequence, a seed, and a combining step. The seed is the accumulator's initial value, so it is also what the fold returns when the sequence is empty, and it fixes the accumulator's type - here an empty totals record. The combining step has the shape `(accumulator, element) -> accumulator`: given the totals so far and one transaction, it returns the totals including that transaction. The fold walks the day's log applying that step once per transaction, carrying the accumulator forward, and returns whatever the accumulator holds at the end. Nothing about the sequence is mutated, and the accumulator's type is free - it need not match the element type, which is why ten thousand transactions can collapse into one record.
code
pseudocode · 11 linesfunction fold(items, seed, combine)
accumulator = seed
for each item in items
accumulator = combine(accumulator, item)
return accumulator
function postSale(totals, transaction)
return { count: totals.count + 1,
takings: totals.takings + transaction.amount }
dayTotals = fold(transactions, { count: 0, takings: 0 }, postSale)go deeper
Be able to name all three inputs - structure, seed, combining step - and state the step's shape as accumulator plus element in, accumulator out. Then say what an empty sequence returns.
Explain why the accumulator type is free, and show two folds over the same log whose results have different types. Say plainly what separates a fold from a stage that preserves the structure's shape.
Point out that the step's dependence on only its two arguments is what later licenses caching the result, reordering the work, or splitting it across workers, and be ready to name what breaks when the step reaches outside itself.
Frame the choice for a team: the most specific operation that does the job reads best, so a fold is the right reach when the result genuinely changes shape and the wrong one when a named per-element stage would have said it.
## The three inputs A **fold** (the same operation is often called a **reduction**) collapses a whole structure into a single value. It takes exactly three things: 1. **The structure** to consume - here, the day's transaction log. 2. **The seed** - the accumulator's starting value, supplied by the caller. 3. **The combining step** - a two-argument function that takes the accumulator so far and one element, and returns the next accumulator. The mechanical shape, with the accumulator threaded from the front of the log: ```pseudocode function fold(items, seed, combine) accumulator = seed for each item in items accumulator = combine(accumulator, item) return accumulator ``` Everything else about folding - direction, identity elements, splitting the work - is a refinement of those three inputs. ## What the seed contributes - **It is the answer for an empty structure.** On a day with no transactions the combining step never runs, and the fold returns the seed unchanged. That is not an edge case bolted on afterwards; it falls straight out of the definition, and it is why a fold needs no special handling for an empty log. - **It fixes the accumulator's type.** Seed the fold with `0` and the accumulator is a number; seed it with an empty totals record and the accumulator is a record. The combining step must then accept and return that same type. - **It is the value the first combination starts from.** Whatever is in the seed is carried into the result, so the seed is a real contribution to the answer and not merely a placeholder. ## What the combining step contributes The step is where all the domain logic lives. Its signature is the whole contract: - It takes **two** arguments - the accumulator and one element - and returns **one** accumulator. - It is the only place an element is examined. A fold itself knows nothing about transactions; it only knows how to thread a value. - It returns a *new* accumulator rather than editing the structure being folded. The source sequence is read, never written. ## Why the accumulator type is free This is the part juniors most often miss: the accumulator does not have to look like the elements. That freedom is what makes a fold the general collapsing operation rather than just a sum. | What you want from the day | Seed | Combining step | Result type | |---|---|---|---| | Total takings | `0` | add the amount | a number | | How many refunds | `0` | add one when the element is a refund | a number | | Full totals record | empty record | post the transaction into the record | a record | | Largest single sale | absent | keep whichever is bigger | one transaction, or absent | | Every card payment | empty list | append when the element is a card payment | a collection | All five are the same fold with different seeds and different steps. Only the last two are interesting shapes, and none of them required a new looping construct. ## Fold against the stages that keep the shape A stage that transforms each element one-for-one, or keeps a subset of them, hands back a structure of the same kind with the same or fewer elements. A fold does not promise that: it promises **one value**, of whatever type the seed chose. Given a thousand transactions, a per-element stage gives you a thousand results and a fold gives you one. That is the whole distinction, and it is the answer an interviewer is listening for. ## Where candidates go wrong - **Calling the seed "the first element".** A seedless reduction that starts from the first element is a *different, narrower* operation: it forces the accumulator to be the element type, and it has no answer at all for an empty sequence. A seeded fold has neither problem. - **Assuming the result must be a number.** Folding into a record, a map, a largest-so-far, or even a collection is routine. - **Describing the step as mutating the source.** The step receives a value and returns a value; the log is untouched, which is what lets the same fold run twice and give the same answer. - **Not being able to state the arity.** `(accumulator, element) -> accumulator` is the sentence to have ready; a candidate who cannot say it usually cannot explain fold direction later either. ## Why interviewers open here Fold is the operation candidates hand-wave most. Mapping and filtering are easy to describe because their result has the same shape as their input. A fold changes shape, and to describe it you have to name the accumulator explicitly - which is exactly the piece a shaky mental model leaves out.
- The accumulator is a totals record while the elements are transactions - does that mismatch break the fold?No. The accumulator's type is chosen by the seed and is independent of the element type; the step only has to have the shape `(accumulator, element) -> accumulator`. A reduction where the two types coincide - summing numbers into a number - is the special case, not the rule.
- What does the fold return for a day with no transactions at all?The seed, unchanged, because the combining step never runs. That is why the seed should normally be the value meaning "nothing has happened yet": an empty record, zero takings, an empty collection.
- If the combining step reads a counter declared outside it, is that still a fold?Structurally yes, but you have given up what the fold was worth. A step that depends on or changes something outside its two arguments makes the result depend on how many times and in what order the fold ran, which blocks caching, reordering and splitting the work later.
A cashier does not re-count the whole drawer after every sale - they keep one running total and add the new amount to it. That running total is the accumulator, and the value it started the shift at is the seed.
saying these in an interview costs you the question
- Calls the seed the first element of the sequence
- Insists the accumulator must have the element's type
- Says the combining step edits the collection being folded
- Cannot say what a fold over an empty sequence returns
- Describes fold as a stage that returns one result per element
- States the combining step as taking one argument