 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2007/ia/paper-5/6/b/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 6 / b / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-14

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 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.

 Read the full article

 New to topics? Read the docs here!