Folding a very long transaction log, what does a left fold do differently from a right fold?

## The bracketing is the difference Write both out for three transactions and the whole question answers itself. With `(+)` standing for any combining step and `z` for the seed: - **left fold**: `((z + t1) + t2) + t3` - the seed is on the **outside left**, and the step is applied as `(accumulator, element)`. - **right fold**: `t1 + (t2 + (t3 + z))` - the seed is on the **inside right**, and the step is applied as `(element, accumulator)`. Two things follow immediately: the argument order of the combining step is swapped, and the grouping runs the other way. Everything else is a consequence of those two. ## When the answers differ If the step is **associative** and the seed is its **identity**, the two folds agree - the grouping cannot be observed. Adding amounts, appending collections and taking the maximum all behave that way. If the step is not associative, they disagree, and the disagreement is not subtle: ```pseudocode fold_left([1, 2, 3], 0, subtract) // ((0 - 1) - 2) - 3 = -6 fold_right([1, 2, 3], 0, subtract) // 1 - (2 - (3 - 0)) = 2 ``` Subtraction, division, averaging a running value with each element, and "keep the newer record on conflict" are all non-associative, and for all of them the direction is part of the specification rather than a stylistic choice. ## What each one costs on a long log | | Left fold | Right fold | |---|---|---| | Step's argument order | `(accumulator, element)` | `(element, accumulator)` | | Natural machine shape | a loop over one accumulator | descend to the end, combine on the way back | | Pending work at peak | one accumulator | one pending combination per element, under eager evaluation | | First output available | only after the last element | possibly after the first element, under non-strict evaluation | | Suits | collapsing a long or streamed log to one value | building a structure lazily, or stopping early | The left fold's shape is the one every imperative loop already has: read an element, update the accumulator, discard the element. Memory does not grow with the log's length, which is why it is the direction that survives a million lines. The right fold's outermost combination is `t1 + <everything after t1>`, so the value on its right-hand side is not known until the end of the log has been reached. Under eager evaluation, where every argument is computed before the step runs, that means the whole chain of pending combinations is outstanding at once and the depth grows with the log. This is the origin of the "it worked in testing and blew up on the production file" story. ## Why a right fold is not simply worse Evaluation strategy changes the picture, and languages differ here: most compute arguments eagerly, some defer them until demanded. If the step **does not force its second argument** - for example it builds a pair whose tail is the pending combination - a right fold can hand back the first piece of its result after seeing one element, and the rest is computed only if someone asks. Two capabilities follow that a left fold does not have: 1. **Early exit.** A step that ignores its accumulator argument on some element ends the fold there, having touched only a prefix of the log. 2. **Unbounded input.** A feed with no end can still be folded, because the fold never needs to reach an end it does not have. A left fold, as normally defined, visits every element before producing anything, so neither of those is available to it. ## Choosing a direction - Collapsing a long or streaming log to a **single accumulated value**: fold left. - Building a **structure** where the front of the result is wanted before the back is computed, or where the consumer may stop early: fold right, if the evaluation strategy supports it. - The step is **not associative**: the direction is dictated by the answer you want, and should be stated explicitly in the code and in the test. - The step **is** associative with an identity seed: pick on cost, because the value is the same either way - and that same associativity is what later lets the work be split across workers. ## What an interviewer is listening for Most candidates say "one goes left to right and the other right to left", which is the visiting order and not the point. The answer that lands names the **bracketing**, produces a non-associative example where the two results differ, and then says what each direction does to a log big enough to matter.