= Solution
Apply <structural recursion> to the original meal, preserving its internal constructors and replacing each leaf:
``
fun gluttony (Snack _) replacement = replacement
| gluttony (Lunch (a, b)) replacement =
Lunch (gluttony a replacement, gluttony b replacement)
| gluttony (Feast (a, b, c)) replacement =
Feast (gluttony a replacement, gluttony b replacement,
gluttony c replacement);
``
The type is `'a meal -> 'b meal -> 'b meal`: original snack labels are discarded, so the replacement can have a different label type. The constructors introduced by the replacement are not recursively processed; only snacks of the original tree are substituted. The immutable replacement can be shared among occurrences without changing the represented value. \b[Every original `Snack` is replaced, while the original internal meal structure is retained.]
Back to article page
