Abstract
In this lecture, we'll look at persistent data structures whose implementation uses " under the hood " imperative structures and in-place mutation, while preserving a purely functional interface. We'll start with Baker's functional arrays, which combine an imperative array and difference lists, then gradually introduce the " fat nodes " technique by Driscoll, Sarnak, Sleator and Tarjan, which gives a systematic procedure for making an imperative tree structure persistent.
