= Solution
Carry the list as an immutable accumulator instead of storing it in a reference:
``
fun snackerPure m =
let
fun collect (Snack x, acc) = x :: acc
| collect (Lunch (a, b), acc) =
collect (b, collect (a, acc))
| collect (Feast (a, b, c), acc) =
collect (c, collect (b, collect (a, acc)))
in
collect (m, [])
end;
``
For any initial accumulator `acc`, <structural induction> shows that `collect(m,acc)` equals the final reference content obtained by traversing `m` left to right and prepending each snack to a reference initially containing `acc`. At `Lunch` and `Feast`, the accumulator passed to each child is the result of all earlier children, exactly matching the imperative sequencing. Thus the result is the \b[reverse of the left-to-right list of snack labels], just as for the original `snacker`; returning the ordinary left-to-right list would be incorrect. The code uses no mutable cells and is polymorphic, with type `'a meal -> 'a list`.
Back to article page
