= Solution
Version snapshots simplify correctness: a complicated command restores the complete prior state, so a bespoke inverse cannot accidentally omit an auxiliary field. Redo restores the recorded result without re-executing behavior that might depend on time, randomness or external input. Restoring an immutable root takes <constant time>, though refreshing the display can cost more.
The storage comparison depends on the representation. A change-specific record for these elementary edits retains only a few indices and song references. Copying a length-$m$ <array> for each of $h$ edits can require $\Theta(hm)$ storage and $\Theta(m)$ copying per edit. A <persistent data structure> with <structural sharing> can preserve many versions much more cheaply; balanced path copying can make small edits allocate $O(\log m)$ new entries. Retaining versions also keeps their reachable data alive. Snapshot references are only constant-sized roots, not a guarantee of constant total retained memory. Neither scheme automatically reverses external effects such as playing audio or writing files. The desired undo boundary must be specified.
Back to article page
