Variadic templates — parameter packs, fold expressions: Visual walkthrough

We will derive the single most important fact about folds: $(x s + \dots) turns x_{1}, x_{2}, \dots, x_{n} into one value, nesting from the right.$

Along the way you'll see why left and right matter, and what breaks when the pile is empty.

Step 1 — What is a "pile of arguments"?

WHAT: we give the pile a name, xs, and label each box.

WHY: you cannot fold something you cannot point at. Before any operator touches the pile, we must agree that xs is not one number — it is a row of numbers. (Trying to treat xs as a single value is the #1 beginner mistake in the parent note.)

PICTURE: three chalk boxes in a row, each with its position tag.

Figure — Variadic templates — parameter packs, fold expressions

In C++ this pile is born from a template parameter pack:

\underbrace{\texttt{auto sum(Ts... xs)}}_{\text{xs = pile of values}}$$ - `typename... Ts` — the `...` **before** the name means *declare a pile of types*. - `Ts... xs` — declare a pile of **values** named `xs`. --- ## Step 2 — What does the operator `+` want? > [!definition] Binary operator > A **binary operator** is a symbol that eats exactly **two** things and returns **one**. Plus does > this: $a + b \to$ one number. "Binary" just means "takes two". See [[Operator Overloading]] for how > `+` can mean this on your own types too. **WHAT:** we notice a mismatch. We have $n$ boxes, but `+` only knows how to swallow **two** at a time. **WHY this tool, not a loop?** A fold is exactly the answer to the question *"I have an operator that takes 2, and a pile of size n — how do I apply it n−1 times to get 1 result?"* That is precisely what `+ ...` will automate. We use `+` (not, say, a for-loop) because we want the compiler to *generate* the chain at compile time — no runtime counter needed. **PICTURE:** the `+` symbol drawn as a mouth that can only bite two boxes; an arrow shows two boxes becoming one. ![[deepdives/dd-coding-5.2.16-d2-s02.png]] So the plan is forced: apply `+` repeatedly, shrinking the pile by one each time. --- ## Step 3 — Where does the `...` go, and what does it mean? > [!definition] The ellipsis in a fold > `...` inside parentheses next to an operator means **"repeat this operator across every box in the > pile"**. The side the `...` sits on is the side that opens up into the whole pile. **WHAT:** we write the fold expression and label every piece. **WHY the parentheses are mandatory:** the same `...` is used elsewhere (declaring/expanding packs), so C++ forces `(...)` around a fold to remove all doubt. Dropping them is a compile error. **PICTURE:** the expression `(xs + ...)` with each symbol annotated: which part names the pile, which part is the operator, which part is "and so on". ![[deepdives/dd-coding-5.2.16-d2-s03.png]] $$\big(\;\underbrace{xs}_{\text{the pile}}\;\underbrace{+}_{\text{operator to repeat}}\;\underbrace{\dots}_{\text{"and the rest"}}\;\big)$$ Because the `...` is on the **right** of the pack, this is a **unary right fold**. "Unary" = no extra starting value; "right" = it nests starting from the right end. We prove that next. --- ## Step 4 — Watch the right fold nest (the core derivation) > [!formula] Unary right fold, exact meaning > $$(\,xs + \dots\,)\;=\;x_1 + \big(x_2 + (\;\dots\; + x_n)\big)$$ > Read it as: the **rightmost** pair joins first, then the next pair to its left wraps around it. **WHAT:** take the concrete pile $xs = 1, 2, 3$ and collapse it. **WHY right-first:** in a right fold the deepest parentheses hug the **last** box, so evaluation begins at $x_n$ and moves leftward. The `...` on the right is your visual cue: *that* side goes deepest. **PICTURE:** three frames. Frame 1: full nesting $1 + (2 + 3)$ with the innermost pair circled. Frame 2: inner pair collapses to $5$. Frame 3: outer pair collapses to $6$. ![[deepdives/dd-coding-5.2.16-d2-s04.png]] Term by term:

(xs + \dots);\to; \underbrace{1}{x_1} + \big(\underbrace{2}{x_2} + \underbrace{3}{x_3}\big) ;=; 1 + \underbrace{5}{\text{rightmost pair first}} ;=; \boxed{6}

- $\;2 + 3\;$ evaluates first — it is inside the deepest parentheses (the right end). - $\;1 + 5\;$ evaluates second — the outer wrap. - One box, value $6$, remains. The fold is done. > [!example] The whole function > ```cpp > template<typename... Ts> > auto sum(Ts... xs) { return (xs + ...); } // sum(1,2,3) == 6 > ``` --- ## Step 5 — Why "left" is a *different* machine (non-associative ops) > [!definition] Associative > An operator is **associative** if the grouping doesn't change the answer: $(a+b)+c = a+(b+c)$. > Plus is associative, so Step 4 gives $6$ either direction. **Subtraction is not.** **WHAT:** fold the same pile with `-` both ways and get **two different answers**. **WHY it matters:** if you blindly copy the `+` fold for `-`, `/`, or string-building, the *direction* silently changes your result. Choosing left vs right is a real decision, not decoration. **PICTURE:** two nesting trees side by side for $1,2,3$: left fold groups the **first** pair first; right fold groups the **last** pair first. Different circled starting points → different totals. ![[deepdives/dd-coding-5.2.16-d2-s05.png]]

\underbrace{(,\dots - xs,)}{\text{left, }...\text{ on left}} = (1 - 2) - 3 = -4 \qquad\neq\qquad \underbrace{(,xs - \dots,)}{\text{right, }...\text{ on right}} = 1 - (2 - 3) = 2

- **Left fold** $(\dots - xs)$: `...` on the left → leftmost pair $1-2$ binds first → $-1$, then $-1-3=-4$. - **Right fold** $(xs - \dots)$: `...` on the right → rightmost pair $2-3$ binds first → $-1$, then $1-(-1)=2$. > [!mnemonic] Which side goes deep? > **The dots point at the pile; whichever side holds the dots is the side that nests deepest.** --- ## Step 6 — The empty pile (the degenerate case) > [!definition] Empty pack > A pile with **zero** boxes. `sum()` called with no arguments. There is nothing for `+` to bite. **WHAT:** ask what $(xs + \dots)$ means when there are no boxes. **WHY it breaks:** `+` needs a starting value (an *identity*) to return when the pile is empty. The C++ standard refuses to invent one for `+`, so a **unary** fold over an empty pack is a **compile error**. Only three operators have built-in empty answers. **PICTURE:** an empty dashed frame. Three operators are allowed to survive it; everyone else hits a red chalk ✗. ![[deepdives/dd-coding-5.2.16-d2-s06.png]] > [!formula] The only legal empty unary folds > $$(\,\dots\;\&\&\;args\,)=\texttt{true},\qquad(\,\dots\;||\;args\,)=\texttt{false},\qquad(\,\dots,\,args\,)=\texttt{void()}$$ --- ## Step 7 — The fix: a binary fold with a seed value > [!definition] Binary fold > A fold that includes a starting value called `init` (the **seed**). Written > $(\,init + \dots + xs\,)$. Now even an empty pile has an answer: just `init`. **WHAT:** add a seed of $0$ so an empty sum returns $0$ instead of failing. **WHY $0$?** $0$ is the **identity** for `+` — adding it changes nothing when boxes exist, and gives the sensible "empty sum = 0" when they don't. This is [[constexpr and Compile-time Computation|compile-time]] safe and never errors. **PICTURE:** the seed box $0$ placed at the left; boxes join onto it one at a time; when the pile is empty only the seed $0$ remains. ![[deepdives/dd-coding-5.2.16-d2-s07.png]]

(,\underbrace{0}_{\text{seed}} + \dots + xs,);\text{on }1,2,3 = ((0 + 1) + 2) + 3 = 6, \qquad\text{on empty} = 0

- With boxes: seed $0$ costs nothing, answer is still $6$. - Empty: no boxes attach, the expression *is* the seed → $0$. **No error.** > [!example] Safe sum > ```cpp > template<typename... Ts> > auto safe_sum(Ts... xs) { return (0 + ... + xs); } // safe_sum() == 0 > ``` --- ## The one-picture summary This final board compresses all seven steps: a pile is named, an operator that eats two is chosen, the `...` says "repeat", the nesting direction is fixed by which side holds the dots, the empty pile is the trap, and a seed is the cure. ![[deepdives/dd-coding-5.2.16-d2-s08.png]] > [!recall]- Feynman retelling — the whole walkthrough in plain words > You have a row of boxes and one name, `xs`, for the whole row (Step 1). You also have a `+` button > that only knows how to squish **two** boxes into one (Step 2). Writing `(xs + ...)` tells the > machine "keep pressing `+` across the whole row" — and the dots on the **right** mean start > squishing from the **right** end (Steps 3–4). For plus it doesn't matter which end you start, but > for minus it absolutely does: starting left gives $-4$, starting right gives $2$ (Step 5). The one > way to break the machine is to feed it an empty row — `+` has no answer for "nothing", so it errors > (Step 6). The fix is to drop a starting box, a seed like $0$, into the row; now even an empty row > answers "$0$", and a full row still answers correctly (Step 7). That's the entire idea: a two-input > button, repeated across a pile, with a direction you choose and a seed for safety. > [!recall]- > A right fold `(xs + ...)` on 1,2,3 nests which pair first? ::: The rightmost, `2 + 3`, giving `1 + (2 + 3) = 6`. > Why does `(xs + ...)` fail on an empty pack? ::: `+` has no identity value defined for the empty case; only `&&`, `||`, `,` do. > How do you make an empty-safe sum? ::: Binary fold with a seed: `(0 + ... + xs)`. > For a non-associative op like `-`, why pick a direction carefully? ::: Left and right give different results, e.g. `-4` vs `2`. --- Related: [[Function Templates]] · [[Templates and Generics]] · [[Recursion]] · [[std::tuple]] · [[Perfect Forwarding]] · [[Operator Overloading]]