A proposal adds a third node kind to a recursively defined hash tree - how should the induction burden it creates weigh in that decision?

This is a design question that the mathematics decides rather than decorates. The shape of a recursive definition fixes the shape of every argument anyone will ever make about it, so the constructor count is a long-lived budget, not a local choice. ## What a constructor costs Structural induction has exactly one obligation per constructor. If a type has `c` constructors and the team maintains `p` proved properties over it, the standing case analysis is about `c * p` cases. Adding a constructor: - adds a case to **each** of the `p` existing arguments, all of which must be reopened, not merely re-read; - adds a case to every future argument, permanently; - adds **interaction** obligations wherever the hypothesis is taken at a child - a combining node must now cope with a child of the new kind, including any assumption it silently made about what children look like; - widens every exhaustive match in the implementation that mirrors the definition, which is where the omission usually shows up first and least informatively. The implementation cost of a third node kind is a day. The reasoning cost recurs at every future change. ## The alternative: pay once with a derived form If the new kind can be *expressed* by the existing ones, define it as sugar: a construction that expands into the core definition before anything is proved about it. | Option | Proof surface | What you still owe | |---|---|---| | New core constructor | Grows by one case in every argument, forever | Every existing proof, reopened | | Derived form that expands | Unchanged | One argument that the expansion preserves meaning | | Keep it out of the type entirely | Unchanged | Handling it outside the structure, where it may not belong | The derived form converts a recurring tax into a single obligation: show that expanding it yields a tree with the intended meaning. Every property already proved of the core then applies to the sugar for free. This is the option teams under-use, because at implementation time the core constructor looks simpler. ## When the new case is worth it The burden is a reason to be deliberate, not a veto. Take the case when: 1. **The kind is genuinely irreducible** - it carries information no arrangement of existing constructors can express, so the expansion would have to lie. 2. **The properties that matter are few and cheap to extend** - two or three claims whose new cases are a line each. 3. **The alternative pushes the distinction outside the type**, where nothing checks it and the invariant becomes a comment. Decline it when the kind is an optimisation in disguise - a pre-combined node, a cached digest, a special empty case - because those are exactly the things a derived form or a separate representation handles without touching what anyone has proved. ## What tests do and do not replace A fair challenge: why prove anything, when generated tests over random trees are cheaper? The honest split: - Generated tests sample **finitely many** structures from a generator with its own biases - usually small, usually balanced, rarely the degenerate spine that breaks a height assumption. They catch the case you forgot to write, fast, and they catch it again after every refactor. - A structural argument covers **every** finitely built tree, including shapes no generator produced, and it tells you *why* the property holds, which is what survives the next change to the definition. They are complements, and the real risk is a third state: proofs written once, a definition changed twice, and nobody re-checking that the case analysis still matches. A proof that no longer matches the type is worse than none, because it is quoted with confidence. So the maintainable answer usually pairs a small constructor set with a short list of properties someone is accountable for re-checking whenever the definition moves. ## How to present the decision Do not argue from elegance. Put a number on it: here are the properties we rely on, here is the case each one gains, here is the interaction case, here is who re-checks them, and here is what the derived form would cost instead. That framing - a recurring reasoning cost against a one-off expansion proof - is the judgment the role actually owns, and it is the same judgment behind keeping the case analysis of any recursive definition small.