In a nested comment thread, how does the shape of the data decide a recursive walker's cases?

## What a recursive data definition actually says A **recursive (inductive) data definition** lists the finite number of ways a value of the type can be built, and says that nothing else is a value of that type. A thread of replies, written that way, is either: - **empty** - no comments at all; or - **a comment followed by the rest of the list** - one comment, plus a reply list that is itself a reply list. And a **comment** is built one way: some text plus a reply list of its own. Two ways to build a list, one way to build a comment, and every thread the program will ever be handed was assembled out of exactly those pieces. That enumeration is not a stylistic note in a design document. It is the specification the walker is written against. ## Reading the cases off the definition Structural recursion is the discipline of letting that enumeration drive the function: 1. Write down every way a value of the type can be built. 2. Give the function exactly one case per way. 3. In each case, name the parts that way carries. 4. Recurse on exactly the parts that have the same type, and combine those results with whatever the case contributes itself. For a reply list, that mechanical procedure produces this: | Way the value was built | Parts it carries | Recursive positions | What the case must produce | |---|---|---|---| | empty list | none | none | the answer for nothing at all - the neutral value | | comment + rest of list | the comment, the rest of the list | the comment's own replies, and the rest | the comment's own contribution combined with both recursive results | Notice how little judgement is left. The number of cases is fixed by the definition. The recursive call sites are fixed by which parts are again threads. The only genuinely free decision is the **combining operation** - addition for a count, concatenation for a flattened list, maximum for a depth - plus the value the empty case returns, which has to be the neutral element of that operation. ## Why derived cases beat guessed ones - **No missing case.** A case per constructor cannot silently omit the empty list, which is the shape a guessed walker most often forgets. - **No invented case.** "A comment with replies" versus "a comment without replies" looks like a third case, but it is not a way a comment is built - it is a test on a comment's reply list, which the list's own two cases already cover. Splitting on it duplicates logic that the recursion handles for free. - **The recursion cannot wander.** Each recursive call is handed a part the current value already carries, so the walker descends the thread it was given rather than re-deriving some other value to walk. - **The code documents the data.** A reader who has never seen the type can reconstruct its definition from the walker's cases, because they are the same list. - **Review is mechanical.** "Is there a case for every way this is built, and does each recursive call take a part?" is a question a reviewer can answer without running anything. ## What the shape decides, and what it leaves open The shape decides the *skeleton*. It does not decide the *meaning*. Counting comments, collecting author names, finding the deepest nesting and rendering an indented view are four different functions with identical case structure and different combining steps. That is exactly the payoff: once the skeleton is derived, the remaining work is small and local, and a bug is almost always in the combining step rather than in the control flow. Several things the shape explicitly does not hand you: - **Visit order.** Handling a comment before descending into its replies, or after, is a free choice; both are structural. - **Cost.** The walker touches every comment once, so the work is proportional to the number of comments in the thread - but the shape says nothing about how expensive the per-comment step is. - **Stack depth.** The number of nested frames follows the *nesting depth* of the thread, which is a property of the data, not something the discipline bounds. - **What to do with a malformed value.** If a thread can arrive with something the definition does not allow, that is a validation concern at the boundary, not another case in the walker. The habit worth building is the first step, not the last: before writing any branch, say out loud the ways a value of this type can be built. The cases follow from that sentence, and a walker whose cases do not line up with it is a walker that will surprise someone.