Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/imperative-programming-resit/6/c/ii/solution

Not necessarily: structural sharing can make snapshots cheap, but the trait alone gives no storage guarantee. With a persistent data structure, unchanged portions of old and new sequences can be shared safely. Saving two root references costs additional space per edit, and adjacent history entries commonly refer to the same intermediate version. With an appropriate balanced persistent tree, each positional edit may add only new vertices, giving approximately storage for retained edits of comparable presentation size, plus references to slides.
There are important qualifications. A fully copied immutable array may allocate per edit and use across its history. A persistent linked list shares suffixes but may copy a long prefix for a late positional edit. Moreover, snapshot history keeps old versions alive that an edit-specific inverse representation might otherwise release. Consequently a significant increase is possible with some implementations or workloads; it is not forced by saving Sequence references, and it cannot be ruled out from the interface alone.

New to topics? Read the docs here!